[BOJ] Q4991 로봇 청소기
[BOJ] Q4991 로봇 청소기Permalink
QuestionPermalink
Language: PythonPermalink
Difficulty: Gold 1Permalink
특정 출발지에서 로봇 청소기를 출발시켜서 더러운 지점들을 모두 청소하기 위해 이동해야하는 최소 이동거리를 구하는 문제로, 더러운 지점의 갯수가 최대 10개이기 때문에 Bruteforce을 활용하여 모든 경우를 고려하여 이동하는 최소 거리를 구할 수 있다.
이때, 각 좌표간에 거리를 구해야하기 때문에 해당 과정에서 bfs을 활용한다.
Solution 1Permalink
from collections import deque
from itertools import permutations
from math import inf
import sys
def find_distances(length,areas):
distances=[[inf] * length for _ in range(length)]
dy=[-1,0,1,0]
dx=[0,1,0,-1]
for i in range(length):
start_row,start_col=areas[i]
queue=deque([(start_row,start_col,0)])
visited=[[inf] * n_cols for _ in range(n_rows)]
#각 점에 대해 bfs을 수행해서 각 좌표까지 도달 가능한 거리 탐색
while queue:
row,col,distance=queue.popleft()
#저장되어 있는 최소 거리보다 크면 해당 점을 탐색할 필요가 없으니 다음 경우 조사
if distance > visited[row][col]:
continue
visited[row][col]=distance
for dir in range(4):
next_row=row+dy[dir]
next_col=col+dx[dir]
#격자 범위를 벗어나는 경우
if next_row < 0 or next_row >=n_rows or next_col < 0 or next_col>=n_cols:
continue
#벽이 있는 경우
if board[next_row][next_col] == "x":
continue
if (distance + 1) < visited[next_row][next_col]:
visited[next_row][next_col]=distance+1
queue.append((next_row,next_col,distance+1))
#각 위치 좌표에 도달하는 거리 초기화
for j in range(i+1,length):
next_row,next_col=areas[j]
distances[i][j]=visited[next_row][next_col]
distances[j][i]=visited[next_row][next_col]
return distances
def solution():
areas=[]
start_row,start_col=0,0
#지나가야하는 좌표 구하기
for row in range(n_rows):
for col in range(n_cols):
if board[row][col] == "o":
start_row,start_col=row,col
if board[row][col] == "*":
areas.append((row,col))
#초기 좌표도 포함시킨다.
areas.insert(0,(start_row,start_col))
length=len(areas)
distances=find_distances(length,areas)
shortest_distance=inf
#더러운 좌표에 대한 순열을 구해서 좌표 순서에 따른 총 이동 거리를 구한다.
for permutation in permutations(range(1,length)):
distance=0
previous_index=0
#시작 좌표를 기점으로 더러운 좌표의 순열을 탐색한다.
for next_index in permutation:
distance+=distances[previous_index][next_index]
previous_index=next_index
shortest_distance=min(shortest_distance,distance)
if shortest_distance == inf:
print(-1)
else:
print(shortest_distance)
if __name__ == "__main__":
while True:
n_cols,n_rows=map(int,input().split())
#입력의 끝
if (n_rows,n_cols)==(0,0):
break
board=[list(input()) for _ in range(n_rows)]
solution()
위와 같이 거쳐야하는 좌표의 갯수가 적은 경우에는 모든 좌표를 고려하는 Bruteforce 방식을 취할 수 있지만, node의 갯수가 많아지면 불가능해진다. 이때는 TSP(Traveling Salesman Problem) 알고리즘을 이용해서 문제를 풀이한다.
from collections import deque
from math import inf
import sys
def find_distances(length,areas):
distances=[[inf] * length for _ in range(length)]
dy=[-1,0,1,0]
dx=[0,1,0,-1]
for i in range(length):
start_row,start_col=areas[i]
queue=deque([(start_row,start_col,0)])
visited=[[inf] * n_cols for _ in range(n_rows)]
#각 점에 대해 bfs을 수행해서 각 좌표까지 도달 가능한 거리 탐색
while queue:
row,col,distance=queue.popleft()
#저장되어 있는 최소 거리보다 크면 해당 점을 탐색할 필요가 없으니 다음 경우 조사
if distance > visited[row][col]:
continue
visited[row][col]=distance
for dir in range(4):
next_row=row+dy[dir]
next_col=col+dx[dir]
#격자 범위를 벗어나는 경우
if next_row < 0 or next_row >=n_rows or next_col < 0 or next_col>=n_cols:
continue
#벽이 있는 경우
if board[next_row][next_col] == "x":
continue
if (distance + 1) < visited[next_row][next_col]:
visited[next_row][next_col]=distance+1
queue.append((next_row,next_col,distance+1))
#각 위치 좌표에 도달하는 거리 초기화
for j in range(i+1,length):
next_row,next_col=areas[j]
distances[i][j]=visited[next_row][next_col]
distances[j][i]=visited[next_row][next_col]
return distances
#TSP을 적용을 위한 dfs
def dfs(n,last,visited):
#모든 지점을 다 순환한 경우
if visited == (1<<n)-1:
return 0
#이미 이전에 처리된 경우이면 중간값 반환
if dp[last][visited] != -1:
return dp[last][visited]
distance=inf
for next_location in range(1,n):
#이미 방문한 경우
if visited & 1<<(next_location) == 1<<(next_location):
continue
#도달할 수 없는 경우
if distances[last][next_location] == inf:
continue
distance=min(distance,dfs(n,next_location,visited | 1<<(next_location)) + distances[last][next_location])
dp[last][visited]=distance
return distance
def solution():
global dp,distances
areas=[]
start_row,start_col=0,0
#지나가야하는 좌표 구하기
for row in range(n_rows):
for col in range(n_cols):
if board[row][col] == "o":
start_row,start_col=row,col
if board[row][col] == "*":
areas.append((row,col))
#초기 좌표도 포함시킨다.
areas.insert(0,(start_row,start_col))
length=len(areas)
distances=find_distances(length,areas)
dp=[[-1] * (1<<length) for _ in range(length)]
shortest_distance=dfs(length,0,1)
if shortest_distance == inf:
print(-1)
else:
print(shortest_distance)
if __name__ == "__main__":
while True:
n_cols,n_rows=map(int,input().split())
#입력의 끝
if (n_rows,n_cols)==(0,0):
break
board=[list(input()) for _ in range(n_rows)]
solution()
댓글남기기