[Python] Baekjoon - 1103. 게임

백준 1103번 게임은 숫자 또는 구멍으로 채워진 게임판에서 구멍에 빠지지 않고 최대로 움직일 수 있는 횟수를 구하는 문제다. 그래프 탐색 또는 다이나믹 프로그래밍 기법으로 해결할 수 있으며 난이도는 골드 2이다.

 

백준 1103번 게임 문제 정보

알고리즘 분류

• 그래프 탐색
• 다이나믹 프로그래밍

난이도

• 골드 2

 

게임 문제 요약

• N * M 크기의 게임판의 각 칸에는 숫자 또는 H(구멍)이 표시되어 있음
• 숫자 칸은 그 칸에 적혀있는 수만큼 상/하/좌/우로 이동 가능
• 구멍에 빠지거나 게임판을 벗어나면 게임 종료
• 왼쪽 맨 위칸에서 출발할 때, 최대로 움직일 수 있는 횟수 구하기(처음 놓는 횟수 포함)

 

문제 풀이 방법

과정

• BFS에 visited를 사용하다가 사이클 판별이 어렵다는 걸 깨닫고 DFS로 변경
  • 현재 경로에서 이미 방문한 적 있는 곳 다시 방문하면 사이클 존재 -> -1 반환 후 종료
• 단순 DFS만 이용하면 시간 초과 -> DP 이용
  • 이번 경로 아니어도 언젠가 방문한 적 있는 곳이면, 그때보다 더 긴 경로로 왔을 때만 계속 진행
  • 따라서 각 칸의 최장 경로의 길이를 저장하는 배열 필요

풀이

• 재귀 함수 getMaxMove(r, c, move)
  • (r,c)에서 움직일 수 있는 다음 좌표로 이동하며 최대 이동 횟수를 구하는 함수
  • checkCycle 배열을 통해 사이클 확인
  • visited배열을 통해 다음 좌표로 이동하는 게 유망한 지 판단

 

코드

# Python3로 제출 시 RecursionError 발생
import sys
sys.setrecursionlimit(10**9)

def goNext(r, c, step, d):
    dr = [1,-1,0,0]
    dc = [0,0,1,-1]
    return r + step * dr[d], c + step * dc[d]


def getMaxMove(r, c, move):
    global N, M, board, visited, checkCycle, max_move

    # 현재 방문이 최장경로이므로 이동횟수 저장
    visited[r][c] = move
    max_move = max(max_move, move)

    for d in range(4):
        if max_move == -1:
            return
        nextR, nextC = goNext(r, c, int(board[r][c]), d)
        nextMove = move + 1
        
        # 다음 좌표가 보드판 내에 있고 구멍이 아닐 때
        if 0 <= nextR < N and 0 <= nextC < M and board[nextR][nextC] != 'H':
                
                # 사이클 체크
                if checkCycle[nextR][nextC]:
                    max_move = -1
                    return
                
                # 다음 좌표에 방문한적이 없거나, 더 긴 경로로 방문하는 경우일 때 방문 
                elif visited[nextR][nextC] == 0 or visited[nextR][nextC] < nextMove:
                    checkCycle[nextR][nextC] = 1
                    getMaxMove(nextR, nextC, nextMove)
                    checkCycle[nextR][nextC] = 0


if __name__ == '__main__':
    N, M = map(int, input().split())
    board = []
    checkCycle = [[0] * M for _ in range(N)]
    visited = [[0] * M for _ in range(N)]
    max_move = 0

    for _ in range(N):
        board.append([*input()])

    visited[0][0] = checkCycle[0][0] = 1
    getMaxMove(0,0,1)
    print(max_move)

추가 Test Case

4 7
2H3H1HH
HHHHHHH
1HHHHHH
2H4H3H2
답: 7

10 10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
답: -1

24 24
12H12H12H12H12H12H12H12H
2HH2HH2HH2HH2HH2HH2HH2HH
HHHHHHHHHHHHHHHHHHHHHHHH
12H12H12H12H12H12H12H12H
2HH2HH2HH2HH2HH2HH2HH2HH
HHHHHHHHHHHHHHHHHHHHHHHH
12H12H12H12H12H12H12H12H
2HH2HH2HH2HH2HH2HH2HH2HH
HHHHHHHHHHHHHHHHHHHHHHHH
12H12H12H12H12H12H12H12H
2HH2HH2HH2HH2HH2HH2HH2HH
HHHHHHHHHHHHHHHHHHHHHHHH
12H12H12H12H12H12H12H12H
2HH2HH2HH2HH2HH2HH2HH2HH
HHHHHHHHHHHHHHHHHHHHHHHH
12H12H12H12H12H12H12H12H
2HH2HH2HH2HH2HH2HH2HH2HH
HHHHHHHHHHHHHHHHHHHHHHHH
12H12H12H12H12H12H12H12H
2HH2HH2HH2HH2HH2HH2HH2HH
HHHHHHHHHHHHHHHHHHHHHHHH
12H12H12H12H12H12H12H12H
2HH2HH2HH2HH2HH2HH2HH2HH
HHHHHHHHHHHHHHHHHHHHHHHH
답: 30