그래프 탐색 문제(경로 탐색)

 

N×M 크기의 게임판이 있습니다.

자동차 미니 게임은 장난감 자동차를 게임판에서 주행하는 게임입니다.

미니 게임에서 자동차가 주행하는 방법은 다음과 같습니다.

• 게임판은 칸마다 0에서 9까지의 숫자가 적혀있습니다. 자동차는 한 번에 각 칸에 적힌 숫자만큼 전부를 이동하며 ↑, ↓, ←, → 방향 중 하나를 골라 움직일 수 있습니다.
• 자동차가 다음으로 움직일 칸이 게임판 밖으로 나가거나 '0'이 적힌 칸인 경우 게임은 종료됩니다.
• 왼쪽 위 (0,0)은 자동차의 출발지이며, 이 칸에 적힌 숫자는 0이 될 수 없습니다.
• 미니 게임판을 줬을 때 자동차가 출발 전, 정차할 칸이 가장 많은 경로를 정합니다.
• 게임이 종료될 때까지 정차한 칸의 개수를 출력하는 프로그램을 작성하세요.
• 출발 칸도 정차한 칸의 개수에 포함합니다.

 

지시사항

입력

첫 번째 줄에 게임판의 세로 길이인 자연수 N, 가로의 길이인 자연수 M을 입력합니다. 1≤N,M≤50

두 번째 줄부터 게임판의 모양대로 숫자를 입력합니다.

출력

첫 번째 줄에 자동차가 정차한 칸의 개수 최댓값을 출력합니다.

자동차가 게임판에서 움직일 수 있는 칸이 무한대인 경우 "-1"을 출력합니다.

 

입력예시

3 5

26051

31264

52451

출력예시

2

 

---

import sys
sys.setrecursionlimit(2500)  # 재귀 깊이 설정 (필요 시 조정 가능)

def dfs(x, y, count):
    global max_count, infinite_loop
    if x < 0 or x >= N or y < 0 or y >= M or board[x][y] == 0:  # 경계검사 + 0칸 도착
        max_count = max(max_count, count - 1)
        return
    
    if in_progress[x][y]:  # 현재 탐색 경로에서 이미 방문한 경우 -> 무한 루프 발생
        infinite_loop = True
        return
    
    if visited[x][y] >= count:  # 이미 더 많이 방문한 적이 있는 경우
        return
    
    visited[x][y] = count
    in_progress[x][y] = True  # 현재 경로에 포함
    
    move = board[x][y]
    
    # 상, 하, 좌, 우 탐색
    dfs(x + move, y, count + 1)
    dfs(x - move, y, count + 1)
    dfs(x, y + move, count + 1)
    dfs(x, y - move, count + 1)
    
    in_progress[x][y] = False  # 경로에서 제외

N, M = map(int, input().split())
board = [list(map(int, input().strip())) for _ in range(N)]

visited = [[-1] * M for _ in range(N)]  # 각 칸을 방문한 적 있는지 추적
in_progress = [[False] * M for _ in range(N)]  # 현재 DFS 경로에서 방문 중인지 추적

max_count = 0
infinite_loop = False
dfs(0, 0, 1)

# 무한 루프가 감지된 경우
if infinite_loop:
    print(-1)
else:
    print(max_count)

 

 

이해 안되는 부분이 너무 많음.

함수부분은 거의 ChatGPT가 써준거 그대로 복붙했다.

 

이해 안되는 것 대충 메모

- sys모듈 기능

- setrecursionlimit()를 삭제했더니 하나의 테스트 케이스에서 오류가 발생한다. 이게 뭐길래?

- 깊이우선탐색(dfs) 예제 더 찾아보기

- dfs함수 전체적인 구조, 경계검사와 0칸 도착 시 max_count 와 count-1 비교, 왜 count-1??

- visited, in_progress 변수 내용 이해 안됨..

 

추후 공부해서 내용 추가할 예정.