이번에는 백준 14497번 주난의 난(難) 문제를 풀어보았습니다.
처음에는 일반적인 BFS 문제라고 생각했습니다.
하지만 이동 가능한 칸인 0은 바로 이동할 수 있고, 친구가 있는 1은 한 번의 점프를 사용해야 지나갈 수 있다는 점이 눈에 들어왔습니다.
즉, 이동 비용이 모두 동일하지 않았기 때문에 단순 BFS로는 해결할 수 없다고 생각했습니다.
이후 문제를 다시 살펴보니 한 번의 점프마다 현재 도달 가능한 영역이 한 겹씩 확장되는 구조였기 때문에 Flood Fill 방식으로 접근하였습니다.
현재 바로 갈 수 있는 위치들은 현재 큐에 넣고, 친구가 있는 위치들은 다음 점프에서 처리할 큐에 넣어 해결하였습니다.
문제 설명
주난이는 현재 위치에서 점프를 하여 주변 친구들을 쓰러뜨릴 수 있습니다.
0: 빈 공간1: 친구- : 주난이
#: 범인
한 번의 점프는 친구들이 있는 한 겹의 영역을 제거합니다.
주난이가 범인에게 도달하기 위한 최소 점프 횟수를 구하는 문제입니다.
풀이 아이디어
처음에는 일반적인 BFS로 생각했지만, 이동 비용이 서로 다르다는 점이 문제였습니다.
0 -> 비용 0
1 -> 비용 1즉, 빈 공간은 현재 점프 안에서 계속 이동할 수 있지만 친구가 있는 위치는 다음 점프가 되어야 이동할 수 있습니다.
그래서 현재 점프에서 이동 가능한 위치는 현재 큐에 넣고, 친구가 있는 위치는 다음 점프에서 탐색할 큐에 저장하였습니다.
현재 큐가 모두 비워지면 점프 횟수를 증가시키고 next_q를 다시 현재 큐로 사용하도록 구현하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int visited[301][301];
int inp_class[301][301];
int dy[4] = {0,0,1,-1};
int dx[4] = {1,-1,0,0};
pair<int, int> friends, junan;
int M,N;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> M >> N;
cin >> junan.first >> junan.second >> friends.first >> friends.second;
for (int i=1; i<=M; i++) {
string s;
cin >> s;
for (int j=1; j<=N; j++) {
if (i == junan.first && j == junan.second) inp_class[i][j] = -1;
else if (i == friends.first && j == friends.second) inp_class[i][j] = 2;
else inp_class[i][j] = s[j-1] - '0';
}
}
int cost = 0;
queue<pair<int, int> > q;
q.push(junan);
visited[junan.first][junan.second] = 1;
while(true) {
queue<pair<int, int> > next_q;
while(!q.empty()) {
pair<int, int> curr = q.front();
q.pop();
if (inp_class[curr.first][curr.second] == 2) {
cout << cost << '\n';
return 0;
}
for (int i=0; i<4; i++) {
int ny = curr.first + dy[i];
int nx = curr.second + dx[i];
if (ny < 1 || ny > M || nx < 1 || nx > N) continue;
if (visited[ny][nx]) continue;
if (inp_class[ny][nx] == 0) {
q.push({ny,nx});
visited[ny][nx] = 1;
} else {
next_q.push({ny,nx});
visited[ny][nx] = 1;
}
}
}
cost++;
q = next_q;
}
return 0;
}풀이 흐름
- 입력을 받아 교실 상태를 저장합니다.
- 주난이 위치를 시작점으로 큐에 넣습니다.
- 현재 점프에서 이동 가능한 위치들을 BFS로 탐색합니다.
- 빈 공간인 경우 현재 큐에 넣습니다.
- 친구가 있는 경우 다음 점프에서 탐색하도록 next_q에 넣습니다.
- 현재 큐가 모두 비워지면 점프 횟수를 증가시킵니다.
- next_q를 현재 큐로 바꾸고 다시 탐색합니다.
- 범인 위치에 도달하면 현재 점프 횟수를 출력합니다.
구현 포인트
1. 현재 점프에서 이동 가능한 영역 확장
빈 공간은 추가 점프 없이 계속 이동할 수 있기 때문에 현재 큐에 넣었습니다.
if (inp_class[ny][nx] == 0) {
q.push({ny,nx});
visited[ny][nx] = 1;
}현재 점프 안에서 계속 Flood Fill이 진행되는 형태입니다.
2. 다음 점프에 처리할 위치 저장
친구가 있는 위치는 현재 점프에서는 통과할 수 없습니다.
그래서 다음 점프에서 처리할 수 있도록 따로 저장하였습니다.
else {
next_q.push({ny,nx});
visited[ny][nx] = 1;
}이 위치들은 다음 점프에서 새롭게 확장되는 영역이 됩니다.
3. 점프 횟수 증가
현재 점프에서 도달 가능한 모든 위치를 탐색한 뒤 점프 횟수를 증가시켰습니다.
cost++;
q = next_q;다음 점프에서는 이전에 저장해둔 위치들부터 다시 탐색을 시작합니다.
4. Flood Fill 방식 사용
이 문제의 핵심이었던 부분입니다.
while(!q.empty()) {
...
}현재 점프에서 이동 가능한 모든 영역을 먼저 확장한 뒤,
queue<pair<int, int> > next_q;다음 점프에 확장될 영역을 따로 관리하였습니다.
한 번의 점프가 한 겹의 친구들을 제거하는 구조와 잘 맞는 방식이었습니다.
5. 범인 도착 확인
현재 탐색 중인 위치가 범인 위치라면 탐색을 종료하였습니다.
if (inp_class[curr.first][curr.second] == 2) {
cout << cost << '\n';
return 0;
}현재 cost가 곧 최소 점프 횟수가 됩니다.
