💡 문제
N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 있다.
게임을 시작하려면 보드의 빈 칸 위에 공을 하나 놓아야 한다. 아래 그림에서 공은 회색 점으로 표시되어져 있다. 게임은 단계로 이루어져 있고, 각 단계는 아래와 같이 구성되어져 있다.
- 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속해서 이동시킨다.
- 공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속해서 이동한다.
게임은 공이 더 이상 이동할 수 없을 때 끝난다. 이 때, 모든 빈 칸을 공이 방문한 적이 있어야 한다.
아래 그림은 총 10단계 만에 모든 칸을 방문하는 방법이다.
보드의 상태가 주어졌을 때, 모든 칸을 방문하기 위한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 보드의 크기를 나타내는 N과 M이 주어진다. N은 세로 크기, M은 가로 크기이고, 두 값은 30보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다. 보드의 상태는 장애물을 나타내는 '*'과 빈 칸을 나타내는 '.'으로 이루어져 있다.
입력으로 주어진 보드가 장애물로만 이루어진 경우는 없다.
출력
각 테스트 케이스마다 보드의 모든 빈 칸을 방문하는 최소 이동 횟수를 출력한다. 출력 형식은 예제를 참고한다.
만약, 모든 빈 칸을 방문할 수 없다면 최소 이동 횟수는 -1이다. 가능한 이동 경로의 수는 1,000,000개를 넘지 않는다.
💭 접근
이 문제는 입력으로 주어지는 보드를 모두 탐색하기 위한 이동경로의 조합을 모두 따져봐야 하는 문제로, 구현이 까다로울 뿐, 기본적인 백트래킹 문제와 크게 다르지 않다.
이 문제를 해결하기 위해선 다음과 같은 순서를 따른다.
- 우선 입력으로 주어진
graph에서 '.'인 모든 칸에서 시작한다.
for i in range(n):
for j in range(m):
if graph[i][j] == '.':
reset_visited()
visited[i][j] = 1
dfs(i, j, 0)이는 가능한 모든 경로를 따져보기 위함이다. 또한 위 코드에서 reset_visited() 함수를 볼 수 있는데, 이는 새로운 지점에서 시작할 때 방문 처리를 해주는 visited 리스트를 초기화하기 위함이다.
def reset_visited():
global visited
visited = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
if graph[i][j] == '*':
visited[i][j] = 1dfs()함수를 실행시켜 백트래킹을 실행한다. 이때 함수의 종료 조건으로check()함수를 볼 수 있는데, 이는 아래 코드와 같이 이제 더이상 나아갈 곳이 없다면 탐색을 종료하고 정답을 갱신할 지 결정한다.
# check() 함수
def check(x, y):
cant_go = True
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
cant_go = False
return cant_go# dfs() 함수의 종료 조건
if check(x, y):
cnt = 0
for i in range(n):
cnt += sum(visited[i])
if cnt == n * m:
flag = True
ans = min(ans, move)
return이때 정답 갱신을 결정하는 방법으론, 우선 더이상 나아갈 곳이 없어 check() 함수를 통과하였다면, 이제 모든 칸을 방문하였는지 확인할 차례이다.
이때 visited 리스트를 0 또는 1로 이루어져 있기 때문에 만약 모든 칸을 방문하고 check()함수를 통과하였다면 visited 리스트의 총 원소의 합은 graph 리스트의 크기인 n * m 과 같을 것이고, 이때 정답을 갱신해주면 된다.
- 2번에서
dfs()함수의 종료조건을 보았으니 이제 탐색하는 방식에 대해 살펴보자.
백트래킹 방식을 사용하여 주어진 보드를 탐색하는 방법은 다음과 같다.
for i in range(4):
nx, ny = x, y
if 0 <= nx + dx[i] < n and 0 <= ny + dy[i] < m and visited[nx + dx[i]][ny + dy[i]] == 0:
while True:
nx += dx[i]
ny += dy[i]
if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
visited[nx][ny] = 1
else:
end_x = nx - dx[i]
end_y = ny - dy[i]
break
dfs(end_x, end_y, move + 1)
while True:
visited[end_x][end_y] = 0
end_x -= dx[i]
end_y -= dy[i]
if end_x == x and end_y == y:
break우선 공은 방향이 정해지면 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지는 계속해서 이동해야 한다. 그렇다면 이대로 while문을 사용하여 이를 구현하는 것은 쉬울 것이다.
그러나 우리는 백트래킹 알고리즘을 사용하고 있기 때문에 다시 보드를 이전 상태로 되돌려야 한다. 따라서 공이 시작했던 좌표와 끝나는 좌표를 각각 저장하고, 이를 사용하여 이전 상태로 되돌려 새로운 경로에 대해서도 탐색할 수 있게 된다.
📒 코드
def dfs(x, y, move):
global ans, flag
if check(x, y):
cnt = 0
for i in range(n):
cnt += sum(visited[i])
if cnt == n * m:
flag = True
ans = min(ans, move)
return
for i in range(4):
nx, ny = x, y
if 0 <= nx + dx[i] < n and 0 <= ny + dy[i] < m and visited[nx + dx[i]][ny + dy[i]] == 0:
while True:
nx += dx[i]
ny += dy[i]
if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
visited[nx][ny] = 1
else:
end_x = nx - dx[i]
end_y = ny - dy[i]
break
dfs(end_x, end_y, move + 1)
while True:
visited[end_x][end_y] = 0
end_x -= dx[i]
end_y -= dy[i]
if end_x == x and end_y == y:
break
def check(x, y):
cant_go = True
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
cant_go = False
return cant_go
def reset_visited():
global visited
visited = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
if graph[i][j] == '*':
visited[i][j] = 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
case_num = 1
while True:
try:
n, m= map(int, input().split())
except:
break
graph = [list(input()) for _ in range(n)]
ans = float('inf')
flag = False
for i in range(n):
for j in range(m):
if graph[i][j] == '.':
reset_visited()
visited[i][j] = 1
dfs(i, j, 0)
print(f'Case {case_num}: {ans}' if flag else f'Case {case_num}: -1')
case_num += 1💭 후기
공이 움직이는 방식을 구현하는 것이 조금 까다로울 뿐, 해결하고 보면 기본적인 백트래킹 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/9944
