목차
마음가짐의 변화
: 그동안 알고리즘 문제를 풀면서 어떻게든 혼자 힘으로 고민해서 푸는 게 좋다고 생각했다.
: 그런데, 그러다보니 어떤 한계에 마주할때마다 자연스레 내 힘으로 풀수 있을만한 문제들만 고르는 나의 모습을 보기 시작했다. 골 하위 문제까지는 어떻게든 풀어본다고 해도 그 이상으로 올라가지 못하는 듯 하다.
: 그래서 단기간 성장 문제집에서 하나씩 풀이를 리뷰하면서
완전히 내 것으로 만드는 연습을 병행하려 한다.
1. 문제
https://www.acmicpc.net/problem/4991
4991번: 로봇 청소기
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
www.acmicpc.net
2. 핵심 아이디어
우선 본 풀이를 시작하기 전에 이 풀이는 다음 블로그에서 참조하였음을 밝힌다.
[Algorithm] BaekJoon : 4991. 로봇 청소기 by Python
문제 바로가기 https://www.acmicpc.net/problem/4991오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.방은 크기가 1×1인 정사각
velog.io
나는 이 아이디어를 풀어서 조금 더 이해하기 쉽게 설명해보고자 한다.
본질적인 아이디어는 동일하다.
본 문제는 기본적으로 순열 문제이다.
순열, 즉 순서가 있는 열을 뜻한다.
즉, 먼지를 청소하는 순서가 전체 경로길이에 영향을 준다.
여기서 이 문제가 까다로워진다.
즉, 출발점과 도착점이 계속 바뀌게 된다.
로봇청소기의 위치에 따라 지금 위치로부터 먼지까지 도달하는 거리를계속 계산해주어야 하는 것이다.
따라서, 이 문제를 쉽게 해결하기 위해선각 먼지간의 거리를 계산하여 2차원 테이블을 만들고먼지에 도달하는 순서에 따라 그 거리를 참고하여 경로길이를 계산하는 것이다.
그럼 예제1를 통해 푸는 과정을 전개해보자
먼저 가구에 있는 곳을 거치지 않고
특정 위치에 도달하는 거리를 반환하는 bfs 함수를 구현해준다.
def bfs(i,j):
visited=[[0]*m for _ in range(n)]
visited[i][j]=1
q= deque([(i,j)])
while(q):
x,y= q.popleft()
for i in range(4):
#상하좌우 탐색
nx= x+dx[i]
ny = y+dy[i]
#범위 오바시=> 건너뜀
if nx<0 or ny<0 or nx>=n or ny>=m:
continue
#아직 방문하지 않았고 가구가 아니라면 -> 방문순서 갱신
if visited[nx][ny]==0:
if data[nx][ny]!='x':
q.append((nx, ny))
visited[nx][ny]= visited[x][y]+1
return visited
1) 먼지와 로봇청소기 위치 잡기
다음으로 좌표로부터 로봇청소기의 위치를 a,b에 넣고먼지들의 위치를 dusts 배열에 담아주겠다.
data= [list(''.join(map(str, input().strip()))) for _ in range(n)]
#1) 더러운 곳과 로봇청소기 위치 잡기
dusts=[] #더러운 곳의 좌표
a,b=0,0 #로봇청소기의 위치
for i in range(n):
for j in range(m):
if data[i][j]=="o":
a,b= i,j
elif data[i][j]=="*":
dusts.append((i,j))
2) 청소기의 초기- 각 먼지 사이의 거리를 갱신
다음으로 첫번째로 접근할 먼지까지의 거리를 cleaner 배열에 담아줄 것이다.
예를 들어 다음 그림에서 각각 a,b,c의 먼지가 있다고 하면
cleaner 배열은 =[a까지의 거리, b까지의 거리,c까지의 거리]로
cleaner=[5, 3, 7]
이 갱신될 것이다.
여기서 거리가 1씩 더 많은 이유는 visited에서
로봇청소기의 초기 시작점을 1부터 갱신했기 때문이다.
그런데, 만약 청소기로부터 먼지까지 갈 수 없다면 어떻게 될까?
그렇다면 그냥 -1을 출력해주면 된다.
청소기로부터 먼지까지 가는 경로가 없기 때문이다.
예를 들어 다음 케이스에선
먼지 위치의 visited는 그대로 0으로 남아있을 것이다.
따라서 청소기로부터 걸리는 먼지까지의 경로거리가 0일 경우에는
is_possible flag를 False로 바꾸어 이번 케이스는 가능하지 않음을 표시해줄 것이다.
2번째 단계를 코드로 나타내면 다음과 같다.
#2) 청소기와 각 먼지까지의 거리 산출
cleaner= [0]* len(dusts) #청소기와 첫번째로 청소할 칸가지의 거리
visited= bfs(a,b) #청소기로부터 각 거리
is_possible=True
for idx, i in enumerate(dusts):
temp= visited[i[0]][i[1]] #청소기- 각 먼지까지의 거리
if temp==0: #갈수가 없다면
print(-1)
is_possible=False
break
cleaner[idx]+=temp-1 #visited를 1부터 시작했으므로
3) 먼지 사이사이 거리 계산
앞서 이야기했듯이 이번 문제에 까다로운 점은
먼지를 어떤 순서로 방문할지 모르기 때문이다.
따라서 먼지 사이사이의 거리를 하나의 테이블로 만들고
출발점과 도착점에 따라 참고해야한다.
예를 들어 다음 a,b,c의 3개의 먼지가 있다고 했을 때
각 먼지까지의 거리 테이블은 다음과 같다.
->visited는 1부터 갱신됨을 잊지 말자
| a | b | c | |
| a | 1 | 7 | 3 |
| b | 7 | 1 | 5 |
| c | 3 | 5 | 1 |
이 테이블을 해석해보자면
a->b로 가는 경로는 6의 거리가 들고
a->c로 가는 경로는 3의 거리가 들고
b->c로 가는 경로는 5만큼 떨어져있음을 의미한다.
즉, 각 먼지를 출발점으로 할때
출발점 먼지를 제외한 다른 먼지까지의 거리를
2차원 테이블로 만들어주는 것이다.
여기까지를 코드로 구현하면 이렇다.
dists= [[0]* len(dusts) for _ in range(len(dusts))] #먼지사이사이의 거리
for i in range(len(dusts)-1):
visited= bfs(dusts[i][0], dusts[i][1]) #이 먼지에서 출발했을 때
for j in range(i+1, len(dusts)):
dists[i][j]= visited[dusts[j][0]][dusts[j][1]]-1 #i번째 먼지- j번째 먼지까지의 거리
dists[j][i]= dists[i][j] #그 반대도 같음
4) 순열에 따른 경로 거리 계산
이제 먼지들의 방문순서를 하나씩 정해줄 타이밍이다.
앞선 예시를 보면
a-b-c의 방문순서는
0-1-2
1-2-0
2-1-0
1-2-1
1-0-2
2-0-1
이렇게 6가지가 나온다.
그럼 이 순서에 따라 각 먼지까지의 거리를 계산하면 된다.
먼저 cleaner에는 청소기 초기위치 - 먼지까지의 거리가 갱신되어 있다.
cleaner=[5, 3, 7]
다음으로 이차원 배열 dists에는 각 먼지까지의 거리가 갱신되어 있다.
| a | b | c | |
| a | 1 | 7 | 3 |
| b | 7 | 1 | 5 |
| c | 3 | 5 | 1 |
그럼 a-b-c 순서로 가는 경로를 temp에 담아보자
temp=0
먼저 청소기 - a - b - c 까지의 거리를
cleaner에서 더해준다.
cleaner=[5, 3, 7]
temp+=5
다음으로 청소기- a - b - c다.
이건 dist에서 더해준다.
| a | b | c | |
| a | 1 | 7 | 3 |
| b | 7 | 1 | 5 |
| c | 3 | 5 | 1 |
temp = 5+7
다음으로 청소기- a - b - c다.
이건 dist에서 더해준다.
| a | b | c | |
| a | 1 | 7 | 3 |
| b | 7 | 1 | 5 |
| c | 3 | 5 | 1 |
temp = 5+7+5
이런 식으로 모든 순을 통해 각 거리를 완전탐색해주면 된다.
answer= sys.maxsize
for case_ in permutations(range(len(dists))): #순열 활용
temp= cleaner[case_[0]] #f로봇- 초기먼지까지의 거리
start= case_[0]
for idx in range(1, len(case_)): #순열을 통해 시작과 도착을 바꿔가면 거리를 잼
end=case_[idx]
temp+=dists[start][end]
start= end
answer= min(answer, temp)
이제 이 코드들을 모두 하나로 합쳐보자
3. 코드
from collections import deque
from itertools import permutations
import sys
dx=[0,0,1,-1]
dy=[1,-1,0,0]
def bfs(i,j):
visited=[[0]*m for _ in range(n)]
visited[i][j]=1
q= deque([(i,j)])
while(q):
x,y= q.popleft()
for i in range(4):
nx= x+dx[i]
ny = y+dy[i]
if nx<0 or ny<0 or nx>=n or ny>=m:
continue
if visited[nx][ny]==0:
if data[nx][ny]!='x':
q.append((nx, ny))
visited[nx][ny]= visited[x][y]+1
return visited
while(1):
m,n= map(int, input().split())
if m+n:
data= [list(''.join(map(str, input().strip()))) for _ in range(n)]
#1) 더러운 곳과 로봇청소기 위치 잡기
dusts=[] #더러운 곳의 좌표
a,b=0,0 #로봇청소기의 위치
for i in range(n):
for j in range(m):
if data[i][j]=="o":
a,b= i,j
elif data[i][j]=="*":
dusts.append((i,j))
#2) 청소기와 각 먼지까지의 거리 산출
cleaner= [0]* len(dusts) #청소기와 첫번째로 청소할 칸가지의 거리
visited= bfs(a,b) #청소기로부터 각 거리
is_possible=True
for idx, i in enumerate(dusts):
temp= visited[i[0]][i[1]] #청소기- 각 먼지까지의 거리
if temp==0: #갈수가 없다면
print(-1)
is_possible=False
break
cleaner[idx]+=temp-1 #visited를 1부터 시작했으므로
if is_possible:
dists= [[0]* len(dusts) for _ in range(len(dusts))] #먼지사이사이의 거리
for i in range(len(dusts)-1):
visited= bfs(dusts[i][0], dusts[i][1]) #이 먼지에서 출발했을 때
for j in range(i+1, len(dusts)):
dists[i][j]= visited[dusts[j][0]][dusts[j][1]]-1 #i번째 먼지- j번째 먼지까지의 거리
dists[j][i]= dists[i][j] #그 반대도 같음
answer= sys.maxsize
for case_ in permutations(range(len(dists))): #순열 활용
temp= cleaner[case_[0]] #f로봇- 초기먼지까지의 거리
start= case_[0]
for idx in range(1, len(case_)): #순열을 통해 시작과 도착을 바꿔가면 거리를 잼
end=case_[idx]
temp+=dists[start][end]
start= end
answer= min(answer, temp)
print(answer)
else:
break4.배운점
압도적인 코드량에 압도되었지만 아이디어 자체는 그리 어렵지 않았던 문제
bfs의 반환값이 값이 아닌 visited 배열일 수도 있다는 점을 잊지 말자
범위를 잘보자
범위가 20x20이면 충분히 완전탐색이 가능하다.
섣부르게 시간초과를 단정짓지 말자
무엇보다 스스로 나의 한계를 짓지 말자
최대한 세계를 넓히자.
'백준 문풀' 카테고리의 다른 글
| [Python] 10942.팰린드롬?(골4) / DP (0) | 2024.01.03 |
|---|---|
| [Python] 1738. 골목길(골1) / 벨만-포드 알고리즘 (0) | 2024.01.01 |
| [Python] 7662. 이중 우선순위 큐(골4) / 최소힙과 최대힙 (0) | 2023.11.24 |
| [백준 500문제 달성] (0) | 2023.11.23 |
| [Python] 나무자르기 - 이분탐색 기본문제 (0) | 2023.11.21 |
