[Python] 백준 9944번 : NxM 보드 완주하기

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

9944번: NxM 보드 완주하기

---

💡 문제 풀이

간단한 구현 문제이다. 백트래킹을 곁들인.

 

백트래킹을 하면서 매번 2차원 배열을 복사하면 메모리가 너무 커지기 때문에

방문했던 좌표들을 처리하는 리스트를 새로 만들었다.

✔️ 느낀 점

어렵지 않은 구현 문제였다. 이전에 예외처리를 하는 문제를 풀어봐서 괜찮았다.

💻 코드

import sys
input = sys.stdin.readline

MAX = 1000001
ans, case = 0, 1

def check():
    for i in range(N):
        if '.' in board[i]: return False
    return True

def backtracking(x,y,cnt):
    global ans
    if check(): ans = min(ans, cnt)
    if cnt < ans:
        for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
            visitedPoints = []
            nx, ny = x, y
            
            while True:
                nx += dx
                ny += dy
                if 0 <= nx < N and 0 <= ny < M and board[nx][ny] == '.':
                    visitedPoints.append([nx, ny])
                    board[nx][ny] = '*'
                else: break
            
            if visitedPoints: backtracking(nx - dx, ny - dy, cnt + 1)
                
            for a, b in visitedPoints:
                board[a][b] = '.'

while True:
    try:
        N, M = map(int, input().split())
        board = [list(input().strip()) for _ in range(N)]
        ans = MAX
        for i in range(N):
            for j in range(M):
                if board[i][j] == '.':
                    board[i][j] = '*'
                    backtracking(i, j, 0)
                    board[i][j] = '.'
        
        if ans == MAX: ans = -1
        print(f'Case {case}: {ans}')
        case += 1
    except:
        break