[백준 파이썬] 1987 알파벳

 

1987번: 알파벳

문제



 

현재 까지 이동한 위치와 다른 알파벳이 그려진 좌표로만 이동할 수 있을 때 가장 멀리 이동하는 거리를 구하는 문제이다.

---

풀이

기본적인 개념은 가장 멀리 떨어진 좌표까지 이동해야 하는 문제이므로 DFS를 사용하였다.

이 때 현재 까지 이동한 알파벳과 다른 알파벳이어야만 이동이 가능하므로 SET자료형을 사용하여 알파벳을 검사해주었다.

visited = set(graph[0][0])

가장 먼저 0, 0일 때의 알파벳을 visited에 추가시켜준다.

def dfs(cnt, r, c):
    global result
    result = max(result, cnt)
    
    for i in range(4):
        nx = r + dx[i]
        ny = c + dy[i]
        
        if 0 <= nx < R and 0 <= ny < C:
            if graph[nx][ny] not in visited:
                visited.add(graph[nx][ny])
                dfs(cnt + 1, nx, ny)
                visited.remove(graph[nx][ny])

 

이 후 위와같이 DFS를 구현했다.

이 때 graph[nx][ny] not in visited 코드를 사용하므로 써 방문한 알파벳과 이동하려는 좌표의 알파벳이 동일한지 확인해준다.

방문하지 않은 알파벳이라면 방문체크를 해준 후 dfs를 재귀하여 탐색을 진행한다.

탐색이 끝난 후에는 방문체크를 해준 알파벳을 Set에서 제거하므로 써 방문기록을 제거한다.

 

코드

import sys
input = sys.stdin.readline
R, C = map(int, input().split())

graph = [list(input()) for _ in range(R)]

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

result = 1

visited = set(graph[0][0])

def dfs(cnt, r, c):
    global result
    result = max(result, cnt)
    
    for i in range(4):
        nx = r + dx[i]
        ny = c + dy[i]
        
        if 0 <= nx < R and 0 <= ny < C:
            if graph[nx][ny] not in visited:
                visited.add(graph[nx][ny])
                dfs(cnt + 1, nx, ny)
                visited.remove(graph[nx][ny])

dfs(result, 0, 0)
print(result)