[파이썬] 백준 1103 : 게임 (골드2)

[파이썬] 백준 1103 : 게임 (골드2)

1103번: 게임

---

문제

---

풀이

0. 방향성 생각

• DFS + DP 사용

1. 입력

import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(input()) for _ in range(h)]
dp = [[-1]*w for _ in range(h)]
visit = [[0]*w for _ in range(h)]
step = [(1,0),(0,1),(-1,0),(0,-1)]

• arr 크기에 맞춰서 방문처리할 visit, 이동거리 저장할 dp필요.

 

2. 함수 정의

def dfs(x,y):

    if visit[y][x]:
        return -1

    if dp[y][x] != -1:
        return dp[y][x]

    visit[y][x] = 1
    dp[y][x] = 0

    for i in range(4):
        dx,dy = step[i]
        nx = x + dx*int(arr[y][x])
        ny = y + dy*int(arr[y][x])
        
        if 0<=nx<w and 0<=ny<h and arr[ny][nx] != 'H':
            temp = dfs(nx,ny)
            if temp == -1:
                return -1

            dp[y][x] = max(dp[y][x],temp+1)

    visit[y][x] = 0
    return dp[y][x]

• 자식 노드에서 탐색하다가 부모 노드로 올라올 수 있다. (사이클 발생)
• 이를 탐지하기 위해서 visit = 1 인 경우 -1을 리턴한다.
• 재귀적으로 호출하기 때문에 리프노드까지 들어가면 현재 지나온 경로에 모두 1이 처리되어있고 함수를 탈출하면서 0으로 만든다. (사실 그래프라서 리프노드라는 말이 정확하지는 않다.)
• 사이클이 한 번 이라도 발생하면 계속 -1을 리턴한다.
• 그렇지 않은 경우 현재 노드에 기록된 dp[y][x]와 하위노드에서 불러온 temp에 +1을 더해 갱신할 값 중 큰 것을 갱신한다. (노드 A에서 한 경로에서 2가 기록되었는데 다른 노드에서 dfs값 3을 가지고 올라오면 갱신해준다)
• 이 때 DP를 사용하지 않으면 계속해서 구해야한다. 한 좌표별로 최대 4개까지 이동할 수 있으므로 맵 사이즈가 작아도 시간복잡도가 지수적으로 증가하므로 DP 사용하기.

3. 출력

answer = dfs(0,0)
if answer == -1: print(-1)
else: print(answer+1)

• 사이클이 발생하는 경우는 -1, 그렇지 않은 경우는 0부터 카운트하므로 1로 처리한다.

 

---

전체코드

import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(input()) for _ in range(h)]
dp = [[-1]*w for _ in range(h)]
visit = [[0]*w for _ in range(h)]
step = [(1,0),(0,1),(-1,0),(0,-1)]

def dfs(x,y):

    if visit[y][x]:
        return -1

    if dp[y][x] != -1:
        return dp[y][x]

    visit[y][x] = 1
    dp[y][x] = 0

    for i in range(4):
        dx,dy = step[i]
        nx = x + dx*int(arr[y][x])
        ny = y + dy*int(arr[y][x])
        
        if 0<=nx<w and 0<=ny<h and arr[ny][nx] != 'H':
            temp = dfs(nx,ny)
            if temp == -1:
                return -1

            dp[y][x] = max(dp[y][x],temp+1)

    visit[y][x] = 0
    return dp[y][x]

answer = dfs(0,0)
if answer == -1: print(-1)
else: print(answer+1)

 

코멘트

DFS + DP 문제는 매일 끼워맞추는 느낌이라 아직 연습이 더 필요하다.

DP 안쓰고 백트래킹만 했을 때 시간초과해서 다시풀었음.. 잘못짜서 초과한거같긴 한데