[Python] 백준 1987번 알파벳

1987번: 알파벳

문제

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

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

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

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

코드

• 정답 코드

import sys
input = sys.stdin.readline

r, c = map(int, input().split())

board = []
for _ in range(r):
    board.append(input())
    
ans = 1

def bfs():
    global ans 
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    q = set([(0, 0, board[0][0])])

    while q:
        x, y, route = q.pop()
        ans = max(ans, len(route))

        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 route:
                q.add((nx, ny, route + board[nx][ny]))

bfs()
print(ans)

시간 초과를 정말 많이 본 문제였다...

처음에 풀이는 

r, c = map(int, input().split())

board = []
for _ in range(r):
    board.append(input())
    
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

visited = [board[0][0]]

def dfs(x, y, visited, num):
    res = num
    
    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 visited:
            new_visited = visited + [board[nx][ny]]
            res = max(res, dfs(nx, ny, new_visited, num + 1))
    return res

print(dfs(0,0,visited, 1))

dfs를 이용하여 풀이하려 했다. 지나온 알파벳을 배열에 저장하고 배열에 저장되어 있지 않은 알파벳이 저장된 칸이라면 계속해서 탐색하는 방법으로 구현하려 했다. dfs를 오랜만에 했더니 잘 기억이 나지 않아 재귀적으로 dfs를 다시 부를 때 지나온 배열을 넘겨주는걸 어떻게 할까 하다가 처음에는 위와 같이 했는데 이렇게 하면 계속 새로운 배열을 만들어서 넘겨주기 때문에 메모리상 정말 비효율적인 코드일 것이다. 그래서 전에 정리해놨던 dfs 코드를 참고 + 구글링하다 얼핏 보니 집합을 이용하는 것 같아서 아래와 같이 구현하고 제출했는데 역시나 시간 초과가 떴다...

r, c = map(int, input().split())

board = []
for _ in range(r):
    board.append(input())
    
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

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

ans = 0

def dfs(x, y, visited, num):
    global ans
    ans = max(ans, num)
    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 visited:
            visited.add(board[nx][ny])
            dfs(nx, ny, visited, num+1)
            visited.remove(board[nx][ny])
dfs(0,0,visited, 1)
print(ans)

이걸 하며 파이썬의 자료구조들의 시간 복잡도가 궁금해져서 찾아봤는데 여기서 사용한 포함 여부를 확인하는 연산의 경우 평균적으로 list  자료형은 시간 복잡도가 O(N), set와 dict 자료형은 O(1)의 시간 복잡도를 가진다고 한다.

 

각 자료형의 다른 연산들에 대한 시간 복잡도는 아래의 링크에서 확인 가능하다.

https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

 

계속 해도 시간 초과로 안돼서 그냥 다른 사람들은 어떻게 했나 찾아봤다. 그랬더니 맨 위의 정답 코드와 같은 풀이를 알게 되었다. 그런데 지금 봐도 잘 이해가 안된다. 내가 풀이한 코드에서도 이미 방문한 알파벳이면 visited에 저장하여 더이상 탐색되지 않도록 처리를 해주었고 정답 코드와 그와 유사한거 같은데 왜 안되는지...