[백준 - Python] 1987. 알파벳 (DFS/BFS)

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

1987번: 알파벳

 

코드

r, c = map(int, input().split())
mat = []
for _ in range(r):
    mat.append(list(input()))
alp = set()
answer = 0

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, count):
    global answer
    #실행된 모든 dfs들 중에서 count와 현재 answer 중 큰 값으로 갱신
    answer = max(answer, count)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c and not mat[nx][ny] in alp:
            alp.add(mat[nx][ny])
            dfs(nx, ny, count+1)
            alp.remove(mat[nx][ny])

alp.add(mat[0][0]) # 좌측 상단 시작값 넣고 Dfs 시작
dfs(0, 0, 1)
print(answer)

 

백트래킹을 활용해야 하는 문제였다.

 

새로 이동한 칸에 적혀 있는 알파벳은, 지금까지 지나온 모든 칸에 적혀 있는 알파벳과

달라야 한다는 조건이 있기 때문에

현재까지 지나온 알파벳을 저장해 두는 변수가 필요하다.

 

해당 변수를 alp라는 집합 자료형을 사용하였고,

좌측 상단부터 순차적으로 dfs를 돌면서 상하좌우 방향을 탐색한다.

 

말이 갈 수 있는 최대 칸 수를 구하는게 문제의 답이므로

max 함수를 통해 탐색하며 실행되는 dfs들 중에서 cnt가 가장 큰 값을

정답값으로 저장한다.

 

위 과정을 수행하기 위해서는 answer값을 전역으로 선언해 주어야 한다.