백준 / 1987번 / 알파벳 / python 파이썬

 

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

 

 

 

---

나의 풀이 (시간 초과)

import sys
input = sys.stdin.readline
R, C = map(int, input().split())

board = [[_ for _ in range(C)]  for _ in range(R)]

for i in range(R):
    alp = input()
    for j in range(C):
        board[i][j] = alp[j]

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

def DFS(x, y, visited, count):
    global max_count
    max_count = max(max_count, count)

    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, count + 1)
            visited.remove(board[nx][ny]) #백트래킹

visited = set()
visited.add(board[0][0])
max_count = 1

DFS(0, 0, visited, 1)
print(max_count)

재귀 기반 DFS로 set()을 이용해 지나온 알파벳을 관리하였으나 시간 초과였다.

DFS에서 재귀 깊이가 깊어지거나 많은 상태를 탐색할 경우 시간 초과가 발생할 수 있다고 한다.

 

새로운 풀이

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

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

def dfs(board, v, visited, depth):
    global ans

    x, y = v
    stack = set()
    stack.add((x, y, visited + board[x][y], depth))

    while stack:
        nx, ny, nowvisited, nowdepth = stack.pop()
        ans = max(ans, nowdepth)
        for i in range(4):
            newx = nx + dx[i]
            newy = ny + dy[i]
            if 0 <= newx < R and 0 <= newy < C and board[newx][newy] not in nowvisited:
                stack.add((newx, newy, nowvisited + board[newx][newy], nowdepth + 1))
    return

dfs(board, (0, 0), '', 1)

print(ans)

 

이 코드는 DFS를 스택을 이용해 반복문으로 구현하고, visited는 문자열로 관리하는 풀이이다.

스택을 사용하는 방식은 재귀에서 발생할 수 있는 중복 호출과 상태 전달 비용이 적고, 반복문을 사용하여 호출 스택을 깊게 쌓지 않아 메모리 오버헤드가 줄어든다.