백준 1987 알파벳 파이썬

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

1987번: 알파벳

 

접근

처음엔 queue 를 사용해 bfs 로 접근했지만, 이 문제는 dfs 로만 풀 수 있다. 

파란색은 BFS 접근을 나타내고, 분홍색은 DFS 식의 접근을 나타낸다. 

문제에서 구하고자 하는 것은 최대한 얼마만큼 뻗어나갈 수 있는지를 구하는 것이기에, 분홍색의 DFS 식으로 접근해야 답을 구할 수 있다.

 

 

코드

r, c = map(int, input().split())
maps = []
for _ in range(r):
    maps.append(list(input()))
ans = 0
alphas = set()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, count):
    global ans
    ans = max(ans, count)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c and not maps[nx][ny] in alphas:
            alphas.add(maps[nx][ny])
            dfs(nx, ny, count+1)
            alphas.remove(maps[nx][ny])
alphas.add(maps[0][0])
dfs(0, 0, 1)
print(ans)

alphas 라는 set 에 방문한 노드의 알파벳을 담는다. 리스트로 담아도 되겠지만, 어차피 중복되는 원소는 필요없기에 set 으로 선언했다.

노드(ny, nx) 가 if 분기문에 해당된다는 의미는, 새롭게 노드를 뻗어나갈 수 있다는 뜻이기에 count 의 값을 + 1 하여 재귀호출한다. 

dfs() 함수가 종료되면 해당 노드(ny, nx) 를 set 에서 빼줘야한다.