백준 1987 [알파벳] 파이썬

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

1987번: 알파벳

# 백준 1987
import sys
input = sys.stdin.readline
R, C = map(int, input().split())
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
field = []
for _ in range(R):
    field.append(list(map(str, input().rstrip())))
visit = [0]*(26)
answer = 0


def dfs(r, c, cnt):
    global answer
    answer = max(answer, cnt)
    for i in range(4):
        row, col = r+dr[i], c+dc[i]
        if 0 <= row < R and 0 <= col < C and visit[ord(field[row][col])-65] == 0:
            visit[ord(field[row][col])-65] = 1
            dfs(row, col, cnt+1)
            visit[ord(field[row][col])-65] = 0


visit[ord(field[0][0])-65] = 1
dfs(0, 0, 1)
print(answer)

DFS로 해결하였는데, pypy에서만 통과하였다.

 

다른 분의 풀이를 보니 BFS로 해결한 분도 계셨다.

 

### BFS set
import sys

R, C = map(int, sys.stdin.readline().split())
board = [list(sys.stdin.readline().strip()) for _ in range(R)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
answer = 1
def BFS(x, y):
    global answer
    q = set([(x, y, board[x][y])])
    while q:
        x, y, ans = q.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if ((0 <= nx < R) and (0 <= ny < C)) and (board[nx][ny] not in ans):
                q.add((nx,ny,ans + board[nx][ny]))
                answer = max(answer, len(ans)+1)

BFS(0, 0)
print(answer)