✅ BFS ✅ 최단거리
상근이가 한칸 이동할 때마다 불도 한칸씩 이동하여 번지므로 상근이가 갈 수 있는 길이 매번 바뀌는 문제이다.
BFS를 사용할건데 상근이가 이동하는 것처럼 불도 이동하므로 queue를 두개 사용하여 각각이 이동하는 하게 풀었다.
// 아래 코드를 데스트 케이스만큼 반복
string map[1001]
queue<pair<int, int>> fire_que, people_que
int dist[1001][1001]
dx[4] = {1, 0, -1, 0}
dy[4] = {0, 1, 0, -1}
BFS(Y, X){
visited[Y][X] = true
people_que.push({Y, X})
dist[Y][X] = 1
while(!people_que.emtpy){
// 1. 불 이동
while(fire_que.size --){ // 불은 동서남북으로 한번씩 모두 이동해줘야 함
x = fire_que.front.second
y = fire_que.front.first
fire_que.pop
for(i : 0 ~ 3){
nx = x + dx[i]
ny = y + dy[i]
if(nx < 0 || ny < 0 || nx >= w || ny >= h) {
flag = true
return
}
if(map[ny][nx] == '#' || map[ny][nx] == '*') continue
map[ny][nx] = '*'
fire_que.push({ny, nx})
}
}
// 2. 사람 이동
x = people_que.front.second
y = people_que.front.first
people_que.pop
for(i : 0 ~ 3){
nx = x + dx[i]
ny = y + dy[i]
if(nx < 0 || ny < 0 || nx >= w || ny >= h) continue
if(map[ny][nx] == '#' || map[ny][nx] == '*') continue
map[ny][nx] = '#' // 이동한 위치는 벽으로 바꾸어 이동할 수 없게 만듦
people_que.push({ny, nx})
dist[ny][nx] = dist[y][x] + 1
}
}
main(){
cin >> w >> h
for(i : 0 ~ h-1){
cin >> map[i]
}
for(i : 0 ~ h-1){
for(j : 0 ~ w-1){
if(map[i][j] == '@') si = i, sj = j
if(map[i][j] == '*') fire_que.push({i,j})
}
}
BFS(si, sj)
if(flag == false) cout << "IMPOSSIBLE"
else cout << dist[ny][nx]
}
O(N^2)
일반적인 문제와 다르게 이동하는 주체가 2개이므로 queue를 2개 사용해야 하는 특이한 문제였고
2개의 주체가 서로의 경로에 영향을 미치므로 이동할 때 분기처리를 또 해줘야 했다.
또한 맨끝 벽에 도달하면 탈출한 것이므로 반복문을 더 돌 필요없이 거리를 출력하고 종료.