👩‍💻🎄 [baekjoon] 1987번: 알파벳

🖍️ solution

import sys
from typing import List

def backtracking(y: int, x: int, count: int, visit: List, graph: List[List]):
    global result
    visit[ord(graph[y][x]) - 65] = True
    result.add(count)

    for i in range(4):
        ny, nx = dy[i] + y, dx[i] + x
        if -1 < ny < r and -1 < nx < c and not visit[ord(graph[ny][nx]) - 65]:
            backtracking(ny, nx, count+1, visit, graph)
            visit[ord(graph[ny][nx]) - 65] = False

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

result = set()
dy, dx = (-1, 1, 0, 0), (0, 0, -1, 1)
grid, visited = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(r)], [False] * 26
backtracking(0, 0, 1, visited, grid)
print(max(result))

💡 idea

• Back Tracking
• 1) 방문 기록 배열 변경
  • 조건 중에서 경로에 알파벳 중복이 불가능하다는 점 이용
  • 전체 격자 사이즈와 동일한 배열 대신 알파벳 사이즈(26)만 선언

일반적인 백트래킹 문제라고 볼 수 있다. 하지만 파이썬으로 해결하려는 경우 시간, 메모리 제한 때문에 빡센 코드 최적화가 필요하다. 격자 문제라서 bfs 선택도 가능한데 그렇다면 python3로도 해결가능하다. 한편, 일반적인 dfs라면 빡센 최적화를 통해 pypy3으로만 통과 가능하다.

문제를 리뷰하던 도중 일반적인 dfs 백트래킹 방식의 비효율성에 대해 고찰해봤다. 아래와 같은 입력이 있다.

IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

일반적인 백트래킹 알고리즘이 탐색하는 과정을 생각해보자. 빨간색으로 칠해진 글자를 IFHE 순서로 탐색했다면, 다음은 F를 탐색해 방문해도 되는지 여부를 판정할 것이다. 이미 F는 방문했기 때문에 아마도 스택 프레임 할당을 취소하면서, 결국에는 I까지 되돌아 갈 것이다.

그리고 다시 오른쪽에 있는 E를 방문한 뒤, FCK 순서로 방문하게 될 것이다. 이 때 들게 되는 의문은 바로 이렇다. 굳이 I까지 되돌아갔다가 탐색해야 할까?? 이미 IE 는 탐색이 가능한 경로라는 것을 우리는 충분히 알 수 있다. 따라서 DP Tabulation 개념을 차용한다면 훨씬 빠르게 풀이가 가능할 것이다.

경로의 유일성을 보장하면서 수정 가능한 자료구조가 필요하기 때문에 배열 대신 세트를 사용해보자. 세트에는 현재까지의 경로 그리고 해당 경로의 마지막 인덱스를 저장해줘야 한다. 같은 경로라고 할 지라도 서로 다른 인덱스에 의해 만들어졌을 가능성이 있기 때문이다. 이렇게 세트를 구성한 뒤, 하나씩 pop해서 경로를 얻어낸다. 그 다음 해당 경로로부터 파생되는 여러 잠재적 경로들을 모두 검사해 경로가 만들어질 수 있는지 여부를 판정하면 된다. 코드는 다음과 같다.

import sys

def dfs(y: int, x: int) -> int:
    dp, result = set(), 0
    dp.add((y, x, grid[y][x]))
    while dp:
        vy, vx, path = dp.pop()
        result = max(result, len(path))
        if result == 26:
            return 26
        for i in range(4):
            ny, nx = dy[i] + vy, dx[i] + vx
            if -1 < ny < r and -1 < nx < c and grid[ny][nx] not in path:
                dp.add((ny, nx, grid[ny][nx] + path))
                
    return result

r, c = map(int, sys.stdin.readline().split())
dy, dx = (-1, 1, 0, 0), (0, 0, -1, 1)
grid = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(r)]
print(dfs(0, 0))

Common BackTracking

DP Tabulation BackTracking

위에는 개선이전 결과고 아래는 개선 이후 결과다. 비약적인 속도 상승하는 동시에 메모리 역시 3배나 덜 사용하는 모습이다. 세트에 있는 유니크한 경로들을 하나씩 꺼내는 방식을 선택했기 때문에 알고리즘 성능이 시드에 영향(set.pop()은 랜덤으로 원소 선택)을 받는다는 점만 감안한다면 매우 좋은 풀이라고 생각한다.