백준 1987 파이썬 풀이 (알파벳, DFS)

기존에 DFS,BFS문제는 주어진 미로에서 가장 짧은 길을 찾거나 걸리는 시간을 주로 구했다. 그런데 이번 문제는 미로가 아닌 각 칸에 알파벳이 주어질때 가장 멀리까지 가는 경우 몇칸이나 지나갈 수 있는지 구하는 것이다.

기존과 달리 모든 경우를 살펴보아야 구할 수 있다.

 

1. DFS로 각 칸은 상하좌우 확인한다.

2. 이때까지 지나온 알파벳과 중복되지 않으면 갈 수 있다.(즉, 해당 경로 혹은 지나왔는지 체크가 되어 있어야 한다.)

 

이렇게 2가지 조건을 통해 코딩을 진행했다. 

r, c = map(int, input().split())
M = []
for i in range(r):
    tmp = list(input())
    M.append(tmp)

alpha = [0]*26
alpha[ord(M[0][0])-65] = 1
s = [[[0, 0], alpha]]
count = 1
dx = [0, 0, 1, -1]  # 동서남북
dy = [1, -1, 0, 0]
while s:
    point, path = s.pop()
    print("point:", point)
    x, y = point
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < r) and (0 <= ny < c) and (path[ord(M[nx][ny])-65] == 0):
            newpath = list(path)
            newpath[ord(M[nx][ny])-65] = 1
            s.append([[nx, ny], newpath])
            if count < sum(newpath):
                count = sum(newpath)
print(count)

이때 짠 코드를 보면 몇가지 문제점이 있다. 중복으로 stack에 저장된 경우를 판별 할 수 없다. 스택에 path배열이 26짜리가 들어가게 되며 list를 그대로 복사하기 때문에 시간이 오래 걸릴 수 있다.

 

고수의 코드를 보면 애초에 stack을 리스트가 아닌 set()으로 설정하고 이때 경로를 문자열로 넣어서 이중배열을 만들지 않고 유지하게 만든다. 

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs():
    result = 1
    queue = set([(0, 0, board[0][0])])

    while queue:
        x, y, visited = queue.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue
            elif board[nx][ny] not in visited:
                next_visited = visited + board[nx][ny]
                queue.add((nx, ny, next_visited))
                result = max(result, len(next_visited))
    return result

r, c = map(int, input().split())
board = []
for i in range(r):
    board.append(list(input()))
print(bfs())

이러한 경우 시간이 훨씬 많이 줄어들게 된다.