[백준] #1987. 알파벳 (python) - 파이썬 풀이 (DFS)

문제

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

1987번: 알파벳

 

문제

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

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

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

 

입력

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

 

출력

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

 

예시 입력

3 6
HFDFFB
AJHGDH
DGAGEH

 

예시 출력

6

 

풀이

import sys

r, c = map(int, sys.stdin.readline().split())
graph = []

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

for _ in range(r):
    graph.append(list(sys.stdin.readline().strip()))

def dfs(sx, sy, visited):
    start_ascii_code = ord(graph[sx][sy]) - 65
    global squares
    squares = max(squares, visited[start_ascii_code])

    for i in range(4):
        nx = sx + dx[i]
        ny = sy + dy[i]

        if (0 <= nx < r) and (0 <= ny < c):
            ascii_code = ord(graph[nx][ny]) - 65
            if not visited[ascii_code]:
                visited[ascii_code] = visited[start_ascii_code] + 1
                dfs(nx, ny, visited)
                visited[ascii_code] = 0

squares = 0
visited = [0]*26
start_ascii_code = ord(graph[0][0]) - 65
visited[start_ascii_code] = 1
dfs(0, 0, visited)
print(squares)

 

말이 최대 어디까지 갈 수 있는지를 탐색하는 것이라서 DFS로 풀었다.

 

1. 방문 여부 확인 및 방문 칸 수 계산

방문 여부랑 지나간 칸 수를 계산하기 위해 visited 변수를 사용했다. 아스키코드를 visited의 인덱스로 사용해 탐색 과정에서 해당 문자를 방문했는지 확인했다.

 

2. dfs 진행

dfs를 진행하는데 여기서 중요한 건 visited[ascii_code] = 0 이다. dfs를 재귀호출하고 빠져나왔을 때 방문했던 곳의 방문여부를 초기화해야 한다. 그래야 dfs를 하기 전의 방문상태로 돌아가게 된다.

 

 

그런데 이 코드를 python으로 제출하면 시간초과가 나서 pypy3로 제출해야 시간초과 없이 통과한다.

그래서 어떻게 하면 python에서 시간초과 없이 코드가 통과할 수 있을지 찾아봤다.

 

 

코드 최적화

 

 

코드 최적화는 이 블로그를 참고해 진행했다.

https://leeingyun96.tistory.com/22

[백준] 1987 알파벳 (파이썬), 시간 초과 해결하는 법

 

import sys

r, c = map(int, sys.stdin.readline().split())
graph = []

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

for _ in range(r):
    graph.append(list(sys.stdin.readline().strip()))

def dfs(sx, sy):
    q = set()
    q.add((sx, sx, graph[sx][sy]))
    squares = 0

    while q:
        x, y, now_visited = q.pop()

        squares = max(squares, len(now_visited))
        if squares == 26:
            return 26

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

            if (0 <= nx < r) and (0 <= ny < c) and graph[nx][ny] not in now_visited:
                q.add((nx, ny, now_visited + graph[nx][ny]))

    return squares

print(dfs(0, 0))

 

이 코드에서는 set을 큐처럼 사용한다. dfs를 재귀형태가 아닌 스택을 사용하는 형태로 구현한다.

나는 문자를 정수로 바꿔서 사용했는데, 이 풀이에서는 문자를 그대로 사용했다.

최대 칸 수도 문자 길이로 계산한다.

 

set를 사용하는 이유

- 이미 방문한 좌표고 동일한 경로인지 확인하기 위해

- set에 방문 좌표와 해당 좌표를 방문하기까지의 경로를 문자들로 추가한다.

 

주의할 점

- set은 pop을 할 때 랜덤으로 요소를 반환한다.

 

 

실행 결과

첫 번째 풀이(최적화 진행 전)

두번째 풀이 (최적화 진행 코드)

 

두 코드의 실행시간과 메모리 차이가 엄청나다. 시간은 약 7배 차이난다.