[백준] 1987번 알파벳 - 파이썬

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

1987번: 알파벳

풀이:

처음에 이 문제를 보고 어떻게 풀어야 할지 고민을 하다 배열을 총 4개 만들어 주기로 결정했다. 지나온 횟수를 저장하는 배열, 지나온 알파벳을 저장하는 배열, 지나온 횟수 중 가장 높은 값을 저장하는 배열, 입력 값을 저장하는 배열. dfs를 실행하여 각 경우의 수마다 그전에 지나온 index가 지닌 지나온 알파벳을 복사해 왔다. 그리고 지나온 횟수를 저장하고 새롭게 지나온 알파벳을 넣어주었다. 그다음 더 이상 길을 찾을 수 없다면 지나온 횟수 중 가장 높은 값을 저장하는 배열에 넣어주었다. 정답은 맞은 것 같았으나 python3는 시간 초과가 나오고 pypy는 메모리 초과가 나왔다.

 

구글링을 통해 지나온 횟수를 저장하는 배열과 지나온 횟수 중 가장 높은 값을 저장하는 배열을 사용하지 않고 정답을 구하는 방법을 배웠다. 간단히 재귀함수를 부를 때 마다 지나온 횟수 + 1을 넣어주면 해결되는 문제였다. 하지만 지나온 알파벳을 저장하는 배열 때문인지 메모리 초과가 나왔다. 결국 지나온 알파벳을 저장하는 배열도 visited라는 26개짜리 True/False로 이루어진 배열을 사용하여 교체해 줬다. 백준 연구소 문제에서 보았던 백트래킹 개념인 듯 보였다. 애초에 문제 분류가 깊이 우선 탐색과 백트래킹이어서 처음에 시도했던 접근법으로는 어림도 없었던 것 같다.

 

이번에 새롭게 배운점은 sys.setrecursionlimit가 메모리를 우선적으로 잡는 개념이어서 sys.setrecursionlimit(10 ** 6)을 하니 메모리 초과가 떴다. 만약 최대 입력값이 100000이면 sys.setrecursionlimit(10 ** 5)으로도 충분하다는 뜻이다.

 

이렇게 제출을 많이 해본적은 처음이었다. 무작정 문제를 풀기보다 이론 공부도 꾸준히 해야겠다.

 

시간초과, 메모리 초과 코드 (오답):

import sys

sys.setrecursionlimit(10 ** 6)


def dfs(x, y):
    for i in range(4):
        if x == 0 and y == 0:
            for a in range(r):
                for b in range(c):
                    numGrid[a][b] = 0
            numGrid[x][y] = 1

        nx = dx[i] + x
        ny = dy[i] + y

        if nx <= -1 or nx >= r or ny <= -1 or ny >= c:
            continue

        if alphaGrid[nx][ny] not in historyGrid[x][y]:
            historyGrid[nx][ny] = historyGrid[x][y][:]
            historyGrid[nx][ny].append(alphaGrid[nx][ny])
            numGrid[nx][ny] = numGrid[x][y] + 1
            numHistoryGrid[nx][ny] = max(numHistoryGrid[nx][ny], numGrid[nx][ny])
            dfs(nx, ny)

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

r, c = map(int, input().split())
alphaGrid = []
for _ in range(r):
    alphaGrid.append(list(map(str, input())))
numGrid = [[0] * c for _ in range(r)]
numHistoryGrid = [[0] * c for _ in range(r)]
historyGrid = [[[] for _ in range(c)] for _ in range(r)]

numGrid[0][0] = 1
numHistoryGrid[0][0] = 1
historyGrid[0][0].append(alphaGrid[0][0])

dfs(0, 0)

print(max(map(max, numHistoryGrid)))

 

백트래킹 개념을 사용한 코드 (정답):

def dfs(x, y, count):
    global answer
    answer = max(answer, count)

    for i in range(4):

        nx = dx[i] + x
        ny = dy[i] + y

        if nx <= -1 or nx >= r or ny <= -1 or ny >= c:
            continue

        if visited[ord(alphaGrid[nx][ny]) - 65] == 0:
            visited[ord(alphaGrid[nx][ny]) - 65] = 1
            dfs(nx, ny, count+1)
            visited[ord(alphaGrid[nx][ny]) - 65] = 0

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

r, c = map(int, input().split())
alphaGrid = []
for _ in range(r):
    alphaGrid.append(list(map(str, input())))

visited = [0] * 26
visited[ord(alphaGrid[0][0])-65] = 1

answer = 1

dfs(0, 0, 1)

print(answer)