문제
문제
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
.: 깨끗한 칸
*: 더러운 칸
x: 가구
o: 로봇 청소기의 시작 위치
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
예제 입력 1
7 5 ....... .o...*. ....... .*...*. ....... 15 13 .......x....... ...o...x....*.. .......x....... .......x....... .......x....... ............... xxxxx.....xxxxx ............... .......x....... .......x....... .......x....... ..*....x....*.. .......x....... 10 10 .......... ..o....... .......... .......... .......... .....xxxxx .....x.... .....x.*.. .....x.... .....x.... 0 0
예제 출력 1
8 49 -1
풀이
진짜 벽느끼게 하는 문제였다..
먼지 간 거리를 bfs나 dfs를 써서 계산해야된다는 건 파악했지만
각 먼지 방문 순서를 순열 리스트로 만든 다음 모든 경우의 수에 대한 최솟값을 계산해야된다는 것까진 생각해내지 못했다..
지선생 도움으로 어찌저찌 풀어내긴 했다😢🤯
❓어떻게 풀까?
- 방 정보에 대한 입력을 받는다
- 이때, 먼지의 위치 정보는
dirty리스트에, 청소기의 위치는start튜플에 저장한다.dirty리스트의 인덱스 0의 값을start로 설정한다.- 즉,
dirty = [(청소기 위치), (먼지1 위치), (먼지2 위치) ...]- 모든
dirty요소에 대한 서로의 최소 거리를 2차원 배열로서 저장한다.
- 서로의 최소 거리는 BFS 알고리즘 함수를 작성해 계산한다.
- 문제에서 먼지 개수는 최대 10개라고 한정해놨기 때문에,
11✕11 2차원 배열을 만든다 (시작점 1 + 먼지 최대 10개)
👆 요런 넉김
- 위 배열 빈칸에 각 먼지 간 거리를 계산해 넣는다.
- 모든 순열의 경우의 수를 구해 각 순열에 대한 이동 거리의 최솟값을 프린트한다.
0(시작 위치)로 시작하는 모든 순열을 구하고- 각 순열에 대한 최소 거리 수를 구한다.
- 현재까지의 최솟값보다 작다면, 최솟값에 현재 거리를 저장한다.
1️⃣ 방의 정보를 입력 받는다.
while True:
w, h = map(int, input().split())
if w == 0 and h == 0: # 0, 0이 입력되면 종료
break
room = [list(map(str, input().strip())) for _ in range(h)] # 방 정보 입력
dirty = [] # 더러운 칸의 좌표 저장
start = () # 로봇 청소기의 시작 위치 저장
for i in range(h):
for j in range(w):
if room[i][j] == '*': # 더러운 칸일 경우
dirty.append((i, j)) # dirty 리스트에 추가
if room[i][j] == 'o': # 로봇 청소기의 시작 위치일 경우
start = (i, j) # start 변수에 저장
dirty.insert(0, start) # 시작 위치를 dirty 리스트의 첫 번째 요소로 삽입❓입력받을 때 strip() 하는 이유
- input받은 한 줄을
str형식으로 바꿔주고, 이를 리스트로 저장한다. int형식을 쓰면 줄바꿈 문자\n를 무시하지만,str은 아니다.- 따라서, 의도치 않은
\n이 저장되는 것을 방지하기 위해strip()을 쓴다.
2️⃣ 서로의 최소 거리를 2차원 배열로서 저장한다.
dist = [[0]*11 for _ in range(11)] # 각 칸 사이의 최소 이동 거리를 저장할 리스트
ok = True # 도달할 수 있는 칸이 있냐 없냐를 저장하는 변수
for i in range(len(dirty)): # 각 칸 사이의 최소 이동 거리 계산
for j in range(i+1, len(dirty)):
dist[i][j] = dist[j][i] = bfs(dirty[i][0], dirty[i][1], dirty[j][0], dirty[j][1])
if dist[i][j] == -1: # 도달할 수 없는 칸이 있다면
ok = False # ok 변수를 False로 설정
if not ok: # 도달할 수 없는 칸이 있다면
print(-1) # -1 출력 후 다음 테스트 케이스로 이동
continue3️⃣ 최소 거리 탐색하는 BFS 함수
# 방향 벡터 설정: 오른쪽, 왼쪽, 아래, 위
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# (x, y)에서 (tx, ty)까지의 최소 이동 거리를 반환하는 BFS 함수
def bfs(x, y, tx, ty):
visited = [[0]*w for _ in range(h)] # 방문 여부 및 이동 거리 저장
queue = deque() # BFS를 위한 큐 생성
queue.append((x, y))
visited[x][y] = 1
while queue:
x, y = queue.popleft()
# 목표지점에 도달하면 이동 거리 반환
if x == tx and y == ty:
return visited[tx][ty] - 1
# 상하좌우로 이동
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or nx >= h or ny < 0 or ny >= w: # 방의 범위를 벗어나면 무시
continue
if room[nx][ny] == 'x' or visited[nx][ny]: # 가구가 있거나 이미 방문한 칸이면 무시
continue
visited[nx][ny] = visited[x][y] + 1 # 이동 거리 갱신
queue.append((nx, ny)) # 큐에 삽입
# 목표지점까지 도달할 수 없으면 -1 반환
return -1시작 위치
(x, y)에서 목표 위치(tx, ty)까지의 최단 거리를 계산하는 함수
BFS (너비 우선 탐색) 알고리즘 사용
-
함수는 먼저 각 위치에 대한 방문 여부와 그 위치까지의 최단 거리를 기록하기 위한 2차원 배열
visited를 초기화한다.
방문하지 않은 위치는 0으로 초기화한다. -
시작 위치
(x, y)를 큐에 넣고, 그 위치를 방문했음을 표시한다.
(즉,visited[x][y]를 1로 설정한다) -
큐에서 가장 먼저 들어온 요소를 꺼내서, 그 위치에서 상하좌우로 이동 가능한 위치를 확인한다. 이때, 다음의 조건을 모두 만족하는 위치만을 큐에 추가하고 방문했음을 표시한다:
- 해당 위치가 방의 범위를 벗어나지 않아야 함
- 해당 위치에 가구('x')가 없어야 함
- 해당 위치를 아직 방문하지 않았어야 함
-
큐에 들어있는 요소가 없을 때까지, 즉 모든 가능한 위치를 방문할 때까지 위의 과정을 반복한다.
-
위의 과정이 끝났을 때, 목표 위치
(tx, ty)에 도달했다면visited[tx][ty] - 1을 반환한다.-1을 하는 이유는 방문 여부 배열visited가 1부터 시작했기 때문이다. -
그러나 목표 위치
(tx, ty)에 도달하지 못했다면-1을 반환한다. 이는 시작 위치에서 목표 위치까지 도달할 수 없음을 나타낸다.
4️⃣ 순열
# 모든 더러운 칸을 방문하는 순서의 모든 경우의 수에 대해 최소 이동 거리 계산
pmt = list(permutations([i for i in range(1, len(dirty))], len(dirty) - 1))
answer = float('inf') # 최소 이동 거리를 저장할 변수
for p in pmt:
current = 0
total = 0
for next in p:
total += dist[current][next] # 이동 거리 누적
current = next
answer = min(answer, total) # 최소 이동 거리 갱신
print(answer) # 최소 이동 거리 출력❓ answer = float('inf') 하는 이유
float('inf')는 무한대를 의미하는 특수한 값이다.- 이는 어떤 실수보다도 크므로, 첫 번째 거리 계산이 이루어질 때 어떤 값이든
answer보다 작거나 같아서answer가 그 값으로 갱신될 수 있도록 해준다. - 이 방법은 최소값을 찾는 문제에서 자주 사용된다.
소스코드
import sys
from collections import deque
from itertools import permutations
input = sys.stdin.readline
# 방향 벡터 설정: 오른쪽, 왼쪽, 아래, 위
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# (x, y)에서 (tx, ty)까지의 최소 이동 거리를 반환하는 BFS 함수
def bfs(x, y, tx, ty):
visited = [[0]*w for _ in range(h)] # 방문 여부 및 이동 거리 저장
queue = deque() # BFS를 위한 큐 생성
queue.append((x, y))
visited[x][y] = 1
while queue:
x, y = queue.popleft()
# 목표지점에 도달하면 이동 거리 반환
if x == tx and y == ty:
return visited[tx][ty] - 1
# 상하좌우로 이동
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or nx >= h or ny < 0 or ny >= w: # 방의 범위를 벗어나면 무시
continue
if room[nx][ny] == 'x' or visited[nx][ny]: # 가구가 있거나 이미 방문한 칸이면 무시
continue
visited[nx][ny] = visited[x][y] + 1 # 이동 거리 갱신
queue.append((nx, ny)) # 큐에 삽입
# 목표지점까지 도달할 수 없으면 -1 반환
return -1
while True:
w, h = map(int, input().split())
if w == 0 and h == 0: # 0, 0이 입력되면 종료
break
room = [list(map(str, input().strip())) for _ in range(h)] # 방 정보 입력
dirty = [] # 더러운 칸의 좌표 저장
start = () # 로봇 청소기의 시작 위치 저장
for i in range(h):
for j in range(w):
if room[i][j] == '*': # 더러운 칸일 경우
dirty.append((i, j)) # dirty 리스트에 추가
if room[i][j] == 'o': # 로봇 청소기의 시작 위치일 경우
start = (i, j) # start 변수에 저장
dirty.insert(0, start) # 시작 위치를 dirty 리스트의 첫 번째 요소로 삽입
dist = [[0]*11 for _ in range(11)] # 각 칸 사이의 최소 이동 거리를 저장할 리스트
ok = True
for i in range(len(dirty)): # 각 칸 사이의 최소 이동 거리 계산
for j in range(i+1, len(dirty)):
dist[i][j] = dist[j][i] = bfs(
dirty[i][0], dirty[i][1], dirty[j][0], dirty[j][1])
if dist[i][j] == -1: # 도달할 수 없는 칸이 있다면
ok = False # ok 변수를 False로 설정
if not ok: # 도달할 수 없는 칸이 있다면
print(-1) # -1 출력 후 다음 테스트 케이스로 이동
continue
# 모든 더러운 칸을 방문하는 순서의 모든 경우의 수에 대해 최소 이동 거리 계산
pmt = list(permutations([i for i in range(1, len(dirty))], len(dirty) - 1))
answer = float('inf') # 최소 이동 거리를 저장할 변수
for p in pmt:
current = 0
total = 0
for next in p:
total += dist[current][next] # 이동 거리 누적
current = next
answer = min(answer, total) # 최소 이동 거리 갱신
print(answer) # 최소 이동 거리 출력