[코딩인터뷰] 백준 1987번

백준 1987번

DFS

import sys
sys.setrecursionlimit(10 ** 5)

# 세로 R 가로 C
# 같은 알파벳 통과 불가
# (0,0) 포함 시작

def dfs(c, x, y):
    global answer

    if answer < c:
        answer = c

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx < R and 0 <= ny < C:
            if not visited[nx][ny] and not alphabet[board[nx][ny]]:
                alphabet[board[nx][ny]] = True
                visited[nx][ny] = True
                dfs(c + 1, nx, ny)
                visited[nx][ny] = False
                alphabet[board[nx][ny]] = False


R, C = map(int, input().split())
board = []
for _ in range(R):
    board.append(list(map(lambda a: ord(a) - 65, input())))

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

answer = 1
alphabet = [False] * 26
alphabet[board[0][0]] = True
visited = [[False] * C for _ in range(R)]
visited[0][0] = True

dfs(1, 0, 0)
print(answer)

BFS

deque 를 사용하면 통과를 못하고, set 을 사용해야 통과할 수 있다는게 신기하면서도 이상하네요.

from collections import deque

R, C = map(int, input().split())
board = []
for _ in range(R):
    board.append(list(input()))

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

answer = 1

q = set([(0, 0, board[0][0])])
while q:
    x, y, h = q.pop()

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx < R and 0 <= ny < C:
            if board[nx][ny] not in h:
                q.add((nx, ny, h + board[nx][ny]))
                answer = max(answer, len(h) + 1)

print(answer)