[Python] 백준 1987번 - 알파벳

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

1987번: 알파벳

 

이 문제를 어렵게 풀게 된 이유는 크게 두 가지가 있다.

 

 

첫 번째는 visited 배열을 알파벳 개수에 맞춰 만들지 않고 입력받은 알파벳 리스트의 해당 인덱스를 1로 바꾸어주는 방법을 선택했다는 점이다. 그리고 같은 알파벳을 두 번 이상 지나갈 수 없으므로 check 리스트에 해당 알파벳을 append 하여 중복을 확인하는 방식이었다.

ex) 
CAAB   이 경우, C를 지나갔다고 하면 1AAB
ADCB                               ADCB

그리고 check.append(c)를 해서
check = [c]
이런 식으로 문제를 풀었다.

처음부터 visited = [0]*26 이렇게 해서 해당 알파벳이 나오면 해당 인덱스의 요소를 1로 바꾸어주는 방식을 선택했다면 문제 접근이 좀 더 쉬웠을 것 같다.

이렇게 하려면 알파벳을 입력 받을 때 바로 ord 함수를 사용해서 알파벳을 아스키코드 값으로 바꾸어주는 게 편리할 것 같아 그렇게 바꿔주었다. 다른 풀이를 보니 이 부분에서 람다를 사용하길래 나도 참고하였다. 

 

 

 

두 번째는.. 첫 번째 이유 때문에 발생한 문제 같다. (정확히는 모름)

입력 받은 알파벳들을 alph라는 리스트 변수에 넣어주었는데 dfs 함수를 돌면서 새로운 경로를 찾을 때는 이전 경로에서 지나간 알파벳들을 기존의 것으로 바꾸어주어야 했기 때문에 리스트 alph1에 alph의 원형을 deepcopy 하였다. (지나간 알파벳은 알파벳이 아니라 1로 바뀌기 때문에 그 1을 다시 알파벳으로 바꿔주어야 했음)

 

근데 deepcopy를 하는데... 중간에 갑자기 deepcopy 했던 것이 풀리는? 일이 발생했다. alph1은 그대로 alph의 원형을 가지고 있어야 하는데 잘 가다가 갑자기 alph1이 alph와 같은 객체를 가리키게 되는 일이 생겼다..

구글링을 해도 잘 모르겠어서 그냥 deepcopy를 사용하지 않는 방법을 택했다.

visited 여부를 alph 리스트에서 체크하지 않고 알파벳 개수만큼 visited 배열을 만들어서 체크하면(첫 번째 이유) 리스트 복사를 할 필요가 없었다.

 

import sys
input = sys.stdin.readline

def dfs(y, x, s): #s: sum
    global ans
    ans = max(ans, s)
    dxdy = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    for dx, dy in dxdy:
        nx = x + dx
        ny = y + dy
        if -1 < nx < c and -1 < ny < r:
            if check[alph[ny][nx]] == 0:
                check[alph[ny][nx]] = 1
                dfs(ny, nx, s+1)
                check[alph[ny][nx]] = 0

r, c = map(int, input().split())
alph = []
for _ in range(r):
    alph.append(list(map(lambda x: ord(x) - 65, input().strip())))
check = [0]*26 #26: 알파벳 개수
ans = 1
check[alph[0][0]] = 1

dfs(0, 0, ans)
print(ans)

풀이 과정에서의 코드를 따로 저장해두지 않고 바로바로 수정해서 최종 코드만 올린다.