[ 1987 ] [ DFS ] 알파벳

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

---

풀이 과정

---

1. 처음엔 그냥 무턱대고 BFS로 풀이를 진행하였으나.. 큐에 데이터가 너무 많이 들어가게 되서 그런지 메모리 초과가 계속해서 발생하였다ㅜㅜ
2. 그래서 BFS처럼 큐에 데이터가 가득 쌓이지는 않으니까 DFS로 풀이를 바꾸어서 진행하였다.
   1. 현재 위치에서 동,서,남,북으로 다음 위치로 이동할 때, 다음 위치에 있는 말이 이전까지 방문한 알파벳에 포함되어있지 않다면 DFS 진행
   2. 재귀함수를 호출하면서 다음 방문 위치와 현재 방문한 알파벳들도 같이 넘겨주어야 한다.
   3. DFS를 진행하면서 최대 이동 거리를 계속해서 갱신시켜준다. 
3. 큐에 데이터가 많이 쌓이게 되면 메모리 초과가 발생하니 BFS뿐 아니라 DFS로도 풀이를 해야 하는걸 배움. 또한 방문처리 할때 set 자료구조에 너무 의존하지 말고, 알파벳은 최대 26개이니까 방문 알파벳들을 문자열로 쭉 연결한 다음 set 연산자가 아닌 in 연산자를 사용하여도 크게 문제될 건 없어보임.

---

소스 코드

---

import sys

input = lambda: sys.stdin.readline().rstrip()
R, C = map(int, input().split())

matrix = [list(input()) for _ in range(R)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0

def solve(visited_str, x, y):
    global R, C
    skip = True
    answer = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < R and 0 <= ny and ny < C:
            if matrix[nx][ny] not in visited_str:
                skip = False
                answer = max(answer,
                             1 + solve(visited_str + matrix[nx][ny], nx, ny))

    if skip:
        return 1
    else:
        return answer

print(solve(matrix[0][0], 0, 0))