[BOJ/백준] 9944 NxM 보드 완주하기

import sys

sys.setrecursionlimit(10000)
def roll(x,y,vis,cnt,roll_cnt):
    global result,total_cnt
    if total_cnt == cnt:
        result = min(result,roll_cnt)
        return
    if roll_cnt > result:
        return
    vis[x][y] = True
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    for i in range(4):
        move = 1
        nx = x + dx[i]*move
        ny = y + dy[i]*move
        while 0<=nx<N and 0<=ny<M and vis[nx][ny] == False:
            nx = nx + dx[i]
            ny = ny + dy[i]
            move += 1
        if move>1:
            for m in range(1,move):
                nx = x + dx[i]*m
                ny = y + dy[i]*m
                vis[nx][ny] = True
            
            roll(nx,ny,vis,cnt+(move-1),roll_cnt+1)

            for m in range(1,move):
                nx = x + dx[i]*m
                ny = y + dy[i]*m
                vis[nx][ny] = False




tc = 1
while True:
    try:
        N,M = map(int,input().split())
        arr = []
        total_cnt = N*M
        visited = [[False]*M for _ in range(N)]
        for x in range(N):
            temp = list(input())
            for y in range(M):
                if temp[y] == '*':
                    visited[x][y] = True
                    total_cnt -= 1
            
            arr.append(temp)

        result = float('inf')
        for x in range(N):
            for y in range(M):
                if arr[x][y] == '.':
                    copy_visited = [row[:] for row in visited]
                    roll(x,y,copy_visited,1,0)

        if result == float('inf'):
            result = -1
        print(f'Case {tc}: {result}')
        tc += 1
    except:
        break

 

 

이 문제는 문제에 주어진 조건대로 굴리면 되는 문제였다.

 

여기서 주의해야할 점은 최소 이동거리가 1이상이어야하고, 그때에만 움직여주면서 VISITED를 반대 상태로 바꿔줬다가, 탐색이 끝나면 원래 상태로 바꿔주는 것이 필요로 했다.

 

또한 최소 이동횟수이므로, 이동횟수보다 많은 로직에 대해서는, 탐색을 그만두고 되돌아가는 백트래킹이 필요로 했다.

 

처음에 최소 이동횟수가 아닌, N*M 보드 완주하는 횟수를 구하는 줄 알고, 잘못 구현하는 실수를 저질렀었다.

 

그점만 조심하면, DFS를 재귀를 짜는것과 비슷하게 풀면 되는 문제였다.