python 백준 1103 게임

• https://www.acmicpc.net/problem/1103
• 코드를 먼저 보고 설명하는게 더 좋을것 같아서 코드를 먼저 올린다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(3000)
def makeArr(R:int,C:int)->list[list]:
    arr = []
    for _ in range(R):
        temp = []
        target = input()
        for i in range(C):
            if target[i].isdigit():
                temp.append(int(target[i]))
            else:
                temp.append(target[i])
        arr.append(temp)
    return arr

def recur(r:int,c:int,cnt:int)->None:
    num = arr[r][c]
    for way in range(4):
        nr,nc = r+num*dr[way], c+num*dc[way]
        if 0<=nr<R and 0<=nc<C and arr[nr][nc] != 'H' and dp[nr][nc]<=cnt:
            if check[nr][nc] == True:
                print(-1)
                exit()
            check[nr][nc] = True
            dp[nr][nc] = cnt+1
            recur(nr,nc,cnt+1) # 재귀
            check[nr][nc] = False

R,C = map(int,input().split())
arr = makeArr(R,C)
check = [[False]*C for _ in range(R)]
dp = [[0]*C for _ in range(R)]
check[0][0] = True
dp[0][0] = 1
dr,dc = (1,0,-1,0),(0,1,0,-1)
recur(0,0,1)
ans = 0
for r in range(R):
    ans = max(ans,max(dp[r]))
print(ans)

makeArr

• 입력으로 주어지는 값이 1~9 숫자 혹은 'H'인데, 숫자일 경우 해당하는 값 만큼 이동을 해야한다.
• 이동 할 때마다 int(arr[r][c]) 형식으로 변환 하는것 보다 arr자체를 변환하는것이 같은 동작을 안해도 되기에 변환

recur

• 기본적으로는 dfs를 구현하기 위해 사용
• check는 순환이 되는지를 확인하는 용도
• dp는 기존에 다른 방법으로 해당 지점에 더 많은 경로를 통해서 온 경우 더이상 알 필요가 없기에 사용(사실상 백트래킹용도)

풀고나서 아쉬운점

• dp에 지금까지 도달한 cnt를 저장하는 것도 좋지만 해당 지점에서 얼마나 멀리 갈 수 있는지를 기록했으면 더 좋았을것 같다
• C지점에서의 최대 이동이 C->D->E 라고 하면 C지점에 2를 기록해두고 A->B->C 로 C지점에 도달했으면 A->B->C + 기존에 기록해둔 2로 확인하는 방법