[백준(BOJ)] #1103- 게임 (파이썬, PyPy3)

문제

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

1103번: 게임

 

---

문제 풀이

처음에 DFS 알고리즘을 적용하여 풀었는데 시간 초과가 발생했습니다. 다른 풀이를 참고하여 DP를 함께 적용하여 풀 수 있다는 것을 알았습니다. 문제 풀이는 다음 이 블로그의 풀이를 참고하여 풀었습니다.

 

2022.07.12 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

[파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

 

1) DFS 알고리즘으로 탐색하여 동전을 최대 몇 번 움직일 수 있는지를 기본으로 한다.

2) 이미 탐색한 곳을 한 번 더 탐색하는 경우는 무한 번 움직일 수 있다는 것을 의미하므로 재방문한 경우는 -1을 출력하고 종료한다.

3) dp 테이블을 이용하여 탐색하는 지점에 저장되어 있는 움직인 횟수가 현재 움직인 횟수보다 크다면 더 이상 탐색하지 않는다. 즉, 이전보다 움직인 횟수가 많은 경우에만 탐색을 진행한다.

 

---

구현

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N, M = map(int, input().split())
    board = [list(input().rstrip()) for _ in range(N)]
    visited = [[False] * M for _ in range(N)]
    dp = [[0] * M for _ in range(N)]
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    max_cnt = 0

    def dfs(tx, ty, cnt):
        global max_cnt
        max_cnt = max(max_cnt, cnt)
        for k in range(4):
            # 네 방향으로 좌표 이동
            x = tx + dx[k] * int(board[tx][ty])
            y = ty + dy[k] * int(board[tx][ty])
            # 움직인 좌표가 범위 안에 있으면서 구멍이 아니고 이전보다 움직인 횟수가
            # 많은 경우에만 탐색 진행
            if 0 <= x < N and 0 <= y < M and board[x][y] != 'H' and cnt + 1 > dp[x][y]:
                # 탐색한 지점이 이미 방문한 지점이면 -1 출력하고 종료
                if visited[x][y]:
                    print(-1)
                    exit()
                else:
                    # 방문 처리
                    visited[x][y] = True
                    dp[x][y] += 1
                    # 움직임
                    dfs(x, y, cnt + 1)
                    # 백트래킹
                    visited[x][y] = False
    dfs(0, 0, 0)
    print(max_cnt + 1)

결과