[Python/파이썬] 백준 9944번 NxM 보드 완주하기

9944번: NxM 보드 완주하기

 

문제

N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 있다.

게임을 시작하려면 보드의 빈 칸 위에 공을 하나 놓아야 한다. 아래 그림에서 공은 회색 점으로 표시되어져 있다. 게임은 단계로 이루어져 있고, 각 단계는 아래와 같이 구성되어져 있다.

• 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속해서 이동시킨다.
• 공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속해서 이동한다.

게임은 공이 더 이상 이동할 수 없을 때 끝난다. 이 때, 모든 빈 칸을 공이 방문한 적이 있어야 한다.

아래 그림은 총 10단계 만에 모든 칸을 방문하는 방법이다.

보드의 상태가 주어졌을 때, 모든 칸을 방문하기 위한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 보드의 크기를 나타내는 N과 M이 주어진다. N은 세로 크기, M은 가로 크기이고, 두 값은 30보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다. 보드의 상태는 장애물을 나타내는 '*'과 빈 칸을 나타내는 '.'으로 이루어져 있다.

입력으로 주어진 보드가 장애물로만 이루어진 경우는 없다.

출력

각 테스트 케이스마다 보드의 모든 빈 칸을 방문하는 최소 이동 횟수를 출력한다. 출력 형식은 예제를 참고한다.

만약, 모든 빈 칸을 방문할 수 없다면 최소 이동 횟수는 -1이다. 가능한 이동 경로의 수는 1,000,000개를 넘지 않는다.

 

코드

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
n, m = 0, 0
blank = 0
ans = int(1e9)

def backtracking(x, y, cnt, move):
    global n, m, blank, ans
    if move >= ans:    # 최소 이동 횟수보다 커지면 더 볼 필요 X
        return
    if cnt == blank:  # 모든 빈 칸 방문 완료
        ans = min(ans, move)
        return
    path = []
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        while 0 <= nx < n and 0 <= ny < m and board[nx][ny] == '.':    # 이동
            board[nx][ny] = '*' # 방문 처리
            path.append((nx, ny))
            nx += dx[i]
            ny += dy[i]
        if path:    # 움직임이 있었음
            backtracking(nx-dx[i], ny-dy[i], cnt+len(path), move+1)
        for i in range(len(path)):   # 방문 처리했던 칸들 다시 원상복구
            r, c = path.pop()
            board[r][c] = '.'
tc = 1    
while True:
    try:
        n, m = map(int, input().split())
        board = []
        blank = 0   # 빈 칸 개수
        for i in range(n):
            board.append(list(input())) # *은 장애물, .은 빈 칸
            for j in range(m):  # 빈 칸 개수 세기
                if board[i][j] == '.':
                    blank += 1

        ans = int(1e9)
        for i in range(n):
            for j in range(m):
                if board[i][j] == '.':
                    board[i][j] = '*'   # 방문 처리
                    backtracking(i, j, 1, 0)
                    board[i][j] = '.'
        print("Case {}: {}".format(tc, ans if ans != int(1e9) else -1))
        tc += 1
    except:
        break

 

백트래킹을 이용해서 풀었다. dfs와 비슷하다고 생각할 수 있는데 백트래킹과 dfs은 보통 재귀의 형태로 구현하는 경우가 많다는 공통점이 있지만 둘이 다른점은 dfs는 모든 경우의 수를 탐색하지만 백트래킹은 불필요한 경우는 가지치기(Pruning)를 통해 더이상 탐색하지 않는다. 이 때문에 백트래킹이 더 효율적이라고 할 수 있다.

 

위 코드의 backtracking 함수에서 이동 횟수가 이미 저장된 최소 이동 횟수보다 크다면 더이상 그 경로는 탐색해볼 필요가 없다. 이 부분이 바로 가지치기를 하는 부분이다.

blank는 보드에 존재하는 빈 칸의 개수이고 cnt는 dfs를 수행하며 지나간 빈 칸의 개수이므로 둘이 같아지면 모든 빈 칸을 탐색했다는 말이므로 이때의 이동 횟수(move)와 ans에 저장된 값 중 작은 값을 ans에 저장하고 리턴한다.

위의 조건들에 걸려서 리턴되지 않았다면 탐색을 진행할건데 진행 가능한 4방향에 대해 모두 살펴보며 이동 가능한만큼 지나간 칸들을 path 배열에 저장하며 나아간다. while문 탈출 후에는 path 배열이 빈 배열인지 아닌지 확인하여 빈 배열이라면 더 이상 이동이 불가능한 것이므로 더 진행하지 않고, path가 빈 배열이 아니라면 backtracking 함수를 재귀적으로 호출한다. 그리고 그 후에는 방문 처리를 위해 '*'로 바꿔줬던 빈 칸들을 다시 빈 칸으로 처리해준다.

따로 board를 deepcopy를 하거나 visited 배열 같은 건 만들지 않고 board 배열에 지나간 칸들은 장애물('*")로 처리하였다가 다시 빈 칸('.')으로 처리해주었다.

 

파이썬에서 입력이 없을 때까지 입력받는 방법은 위 코드와 같이 while문과 try, except 구문을 활용하면 된다.