9944번: NxM 보드 완주하기
N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져
www.acmicpc.net
문제
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 구문을 활용하면 된다.
'문제풀이 > 백트래킹' 카테고리의 다른 글
[Python/파이썬] 백준 6443번 애너그램 (0) | 2023.09.23 |
---|---|
[Python/파이썬] 백준 16986번 인싸들의 가위바위보 (0) | 2023.08.22 |
[Python/파이썬] 백준 16987번 계란으로 계란치기 (0) | 2023.05.05 |
[Python/파이썬] 백준 14888번 연산자 끼워넣기 (0) | 2023.05.04 |
[Python/파이썬] 백준 14712번 넴모넴모 (Easy) (1) | 2023.03.13 |