[백준] 1987. 빙고 python

🐳 링크

백준 1987번 빙고

🐕 문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

🐾 풀이 방법

DFS로 풀었을 땐 시간 초과가 났다.. 그리고 PASSING 을 처음에는 DICTIONARY로 만들어 {65:0,66:1,..} 이런 식으로 아스키 수를 이용해서 구현한 뒤, PASSING[ord('A')] == 0 #지나지 않았음. 이런 식으로 하면 풀리지 않았다. 아마도 다시 백트래킹해가는 과정에서 계속 지났다고 표시되어있어서 그런 것 같다.

BFS로 풀자면, 지나간 알파벳인지를 확인하기 위해 지나갈 때마다 이전 거에 지나간 알파벳을 더해준다. 예를 들자면 원래는 'A' 였다면, 다음번에 'B'를 지날 때 변수 ans는 'A' 에서 'AB' 가 되는 것이다.

solution 코드 (BFS: 통과, DFS: 시간초과)

import sys
sys.stdin = open("input.txt", "rt")
sys.setrecursionlimit(10**5)

dx = [1,-1,0,0]
dy = [0,0,1,-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)



def dfs(x,y,cnt):
    global passing, answer

    answer = max(cnt, answer)
    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 passing):
            passing.append(board[nx][ny])
            dfs(nx, ny, cnt + 1)
            passing.remove(board[nx][ny])



R, C = map(int, sys.stdin.readline().split())
board = list()
for _ in range(R):
    board.append(list(sys.stdin.readline().split().pop()))
passing = list()
passing.append(board[0][0])
answer = 1
# dfs(0,0,1)
bfs(0,0)
print(answer)