백준 / 알파벳 / 1987번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 알파벳 / 1987번 (골드 4단계)

문제 사이트: https://www.acmicpc.net/problem/1987

 

문제 설명

---

나의 풀이

처음에는 BFS로 풀었다

from collections import deque

R, C = map(int, input().split())

board = []

for _ in range(R):
    line = list(input())
    board.append(line)

def bfs(board):
    q = deque([(0, 0)])
    s = set()
    s.add(board[0][0])

    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    steps = 0

    while q:
        y, x = q.popleft()

        for iy, ix in move:
            ny = iy + y
            nx = ix + x
            if 0 <= ny < len(board) and 0 <= nx < len(board[0]) and board[ny][nx] not in s:
                q.append((ny, nx))
                s.add(board[ny][nx])

        steps += 1

    return steps

print(bfs(board))

이 풀이의 문제점은 여러 방향으로 뻗어나가고 있지만 다른 한쪽에서 새로운 알파벳을 지나가면 또 다른 방향에서 다른 한 쪽에서 지나간 알파벳 때문에 새로운 알파벳을 지나갈 수 없다는 단점이 있다.

 

• 방문했던 알파벳을 제대로 관리하지 않음: s 세트에 알파벳을 추가하는 방식이 모든 경로에서 공유되기 때문에, 모든 경로에서 동일한 알파벳을 사용하지 않게 한다.
• 경로 길이를 정확하게 계산하지 않음: steps 변수는 BFS의 각 단계에서 증가하는 방식으로 설정되어 있어서, 실제 최장 경로 길이를 정확히 나타내지 못한다.
• 큐에서 현재 위치를 빼내면서 방문 기록을 공유함: 큐에서 위치를 꺼낼 때, 해당 위치에 도달하는 경로를 따로 추적하지 않아서 경로가 혼합된다.

위의 단점을 보완한 DFS 풀이

R, C = map(int, input().split())

board = []

for _ in range(R):
    line = list(input())
    board.append(line)

def dfs(board, y, x, visited):
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    max_steps = 0

    for iy, ix in move:
        ny = y + iy
        nx = x + ix
        if 0 <= ny < len(board) and 0 <= nx < len(board[0]) and board[ny][nx] not in visited:
            visited.add(board[ny][nx])
            max_steps = max(max_steps, dfs(board, ny, nx, visited))
            visited.remove(board[ny][nx])

    return max_steps + 1

visited = set()
visited.add(board[0][0])
print(dfs(board, 0, 0, visited))

 

DFS를 이용하여 각 경로를 독립적으로 추적하고, 백트래킹을 사용하여 경로를 다시 돌아가면서 최장 경로를 찾을 수 있다.

하지만 이 풀이도 Python3로 제출하면 시간초과가 발생하고 PyPy3로 제출해야 정답이 됐다.

 

이외 다른 풀이

def dfs(board, y, x, visited, memo):
    if memo[y][x][visited] != -1:
        return memo[y][x][visited]

    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    max_steps = 0

    for iy, ix in move:
        ny = y + iy
        nx = x + ix
        if 0 <= ny < len(board) and 0 <= nx < len(board[0]):
            next_char = board[ny][nx]
            next_bit = 1 << (ord(next_char) - ord('A'))
            if not (visited & next_bit):
                max_steps = max(max_steps, dfs(board, ny, nx, visited | next_bit, memo))

    memo[y][x][visited] = max_steps + 1
    return memo[y][x][visited]

R, C = map(int, input().split())
board = [input().strip() for _ in range(R)]

memo = [[[-1] * (1 << 26) for _ in range(C)] for _ in range(R)]
initial_bit = 1 << (ord(board[0][0]) - ord('A'))
print(dfs(board, 0, 0, initial_bit, memo))

이외에 이런 방법을 이용하여 풀 수 있지만 메모리 초과를 하게 되었다.

• 메모이제이션(각 상태에서 최대 경로 길이를 저장하여 이미 계산한 경로를 재사용)
• 비트마스크(방문한 알파벳을 비트마스크로 관리하여 상태를 효율적으로 기록하고 조회)

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/81

깊이 우선 탐색(DFS, Depth-First Search)