[알고리즘 문제 풀이][파이썬] 백준 1103번: 게임

백준 1103 문제 링크: https://www.acmicpc.net/problem/1103

📑 문제 설명
1. 형택이는 1~9까지의 숫자와 구멍이 있는 직사각형 보드에서 게임 진행
2. 보드의 가장 좌상단에 동전을 올려놓고 게임 시작
3. 동적이 있는 곳에 쓰여 있는 숫자 X 확인
4. 상,하,좌,우 중 한 방향을 선택
5. 동전을 4에서 고른 방향으로 X만큼 이동 --> 중간에 있는 구멍 무시
6. 동전이 구멍에 빠지거나 보드 바깥으로 나간다면 게임 종료
7. 최대한 오래동안 이동하며 보드 위에 있는 것이 목표

입력:
세로 N과 가로 M 크기가 주어진다. --> 차례대로 행, 열
그 다음주로 보드의 상태가 주어지며 숫자는 1~9까지의 자연수, 또는 구멍을 상징하는 H이다.

• 단, 시작하는 칸은 H가 아님.

출력:
첫째 줄에 문제의 정답(최대한 동전을 이동하는 횟수)을 출력하며 동전을 무한번 움직일 수 있다면 -1을 출력한다.

💡 문제 해결 방법
알고리즘: DFS

알고리즘 선택 이유
1. 모든 경로 탐색 필요
2. 다시 돌아와서 다른 경로 탐색 필요

예외처리 및 추가 내용
1. 입력 받을 시에 공백이 없기 때문에 문자열로 받은 후 따로 정수로 형변환하여 그래프 저장
2. 좌측 상단에서 시작하여 도착한 곳이 H이거나 N, M을 벗어나는 경우 종료 --> 재귀함수를 호출하여 전역변수에 가장 긴 이동횟수를 기록
3. 사이클 검출 필요 --> DFS로 탐색할 때 이미 방문한 곳을 방문한다면 사이클 존재
4. 방문한 곳을 또 방문할 수 있음

스터디 내용
1. 맵 그래프 읽기
2. dfs + 백트래킹 방법만으로는 시간초과 --> 반드시 dp를 활용하여 풀어야 함

💻 코드

import sys
n, m = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
    temp = sys.stdin.readline()
    graph.append(temp[:-1])

visit = [[False for x in range(m)]for x in range(n)]
dp = [[0 for x in range(m)]for x in range(n)]
def dfs(x, y, dist):
    global maxdist
    maxdist = max(maxdist, dist)
    move = int(graph[x][y])
    adjlist = [[x-move, y], [x+move, y], [x, y-move], [x, y+move]]
    for point in adjlist:
        nx=point[0]
        ny=point[1]
        if nx >=0 and nx<n and ny >= 0 and ny < m and graph[nx][ny] != 'H' and dist + 1>dp[nx][ny]:
            if visit[nx][ny] == False:
                dp[nx][ny] = dist + 1
                visit[nx][ny]=True
                dfs(nx, ny, dist+1)
                visit[nx][ny]=False
            else:
                print(-1)
                exit()

global maxdist
maxdist = -1
dfs(0, 0, 1)
print(maxdist)

💟 추가적으로 알게 된 점
1. DP 위력을 알았다. 최대한 DFS 함수에서 if 문을 통해 필요없는 길은 안 가도록 설정하려고 했으나 역북족. dp를 통해 dist를 비교해주니 갈 필요없는 경로가 배로 제거됨