문제 링크 : https://www.acmicpc.net/problem/9376
9376번: 탈옥
상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타
www.acmicpc.net
이 문제를 푸는 로직은 다음과 같습니다.
1.
기본적으로 죄수1, 죄수2, 상근이가 어느 공통의 문에서 집결할 경우, 탈옥을 했다고 볼 수 있습니다.
때문에 각 구성원들이 문을 딴 횟수를 별도로 저장해서 합산하면 됩니다.
2. 만약 어느 특정한 문에서 3명이 만나게 될 경우, 다음의 값들을 더해주면 됩니다.
상근이가 해당 문까지 도착하기 위해 문을 딴 횟수
+ 죄수1이 해당 문까지 도착하기 위해 문을 딴 횟수
+ 죄수2가 해당 문까지 도착하기 위해 문을 딴 횟수
- 2 (중복값 제거)
여기서 마지막에 -2가 포인트입니다. 문을 따는건 한명이면 족하므로, 나머지 2명에 대한 값을 제거해줘야 합니다.
3. 만약 빈 공간에서 만나는 경우, 2번과 마찬가지로 각자가 빈 공간까지 도착하기 위해 문을 딴 횟수를 모두 더해주면 됩니다. 단, -2를 해줄 필요는 없습니다. 이해가 안될 경우 아래 케이스를 확인하면 됩니다.
4. 3번과 관련해서, 다음과 같은 예시를 주의하셔야 합니다.
정 가운데 있는 '.'의 경우, 빈 공간에 해당되지만 누구도 지나갈 수 없는 위치에 있습니다.
문제 풀이는 다음과 같습니다.
1. 테스트 케이스만큼 while문을 진행합니다.
int t;
cin >> t;
while(t--){
int h,w,y1=0,x1=0,y2=0,x2=0,temp=0,ans=1e9;
cin >> h >> w;
vector<vector<char>> v(h+2,vector<char>(w+2)); // 1
for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
cin >> v[i][j];
if(v[i][j]=='$'&&y1==0){ // 2
y1 = i;
x1 = j;
}
else if(v[i][j]=='$'&&y1!=0){ // 3
y2 = i;
x2 = j;
}
}
}(1) 벡터의 크기를 가로 세로 +2 해주는 이유는, 상근이는 감옥 밖에서 접근하기 때문입니다.
(2) ~ (3) 각 죄수의 위치를 기록합니다.
2. 아래 벡터들은 상근이와 죄수 2명의 누적 잠금해제를 저장한 벡터입니다. 매개변수로 v 벡터와 각자의 위치를 넘겨 받습니다.
vector<vector<int>> d1 = bfs(v,0,0);
vector<vector<int>> d2 = bfs(v,y1,x1);
vector<vector<int>> d3 = bfs(v,y2,x2);
3. 다음은 bfs의 코드입니다.
vector<vector<int>> bfs(vector<vector<char>> &a, int y, int x){
int n = a.size(); // 1
int m = a[0].size();
vector<vector<int>> map(n,vector<int>(m)); // 2
for(int i=0; i<n; i++){
for(int j=0; j<m; j++) map[i][j] = -1; // 3
}
map[y][x] = 0; // 4
deque<pair<int,int>> q; // 5
q.push_front({y,x});
while(!q.empty()){
yy = q.front().first;
xx = q.front().second;
q.pop_front();
for(int i=0; i<4; i++){ // 6
ny = yy+my[i];
nx = xx+mx[i];
if(ny<0||ny>=n||nx<0||nx>=m) continue; // 7
if(a[ny][nx]=='*') continue; // 8
if(map[ny][nx]!=-1) continue; // 9
if(a[ny][nx]=='#'){ // 10
map[ny][nx] = map[yy][xx]+1;
q.push_back({ny,nx});
}
else{ // 11
map[ny][nx] = map[yy][xx];
q.push_front({ny,nx});
}
}
}
return map; // 12
}(1) 매개변수로 넘겨받은 v의 가로 세로 길이만큼 n,m을 설정합니다.
(2) 누적으로 문을 딴 횟수를 저장하기 위한 벡터를 선언합니다. 이하 map이라고 부르겠습니다.
(3) map 벡터는 -1로 초기화합니다.
(4) 현재 위치의 map값은 0으로 저장합니다.
(5) queue가 아닌 deque로 bfs를 진행합니다.
여기서 왜 queue가 안되는지 궁금하실 수 있는데요, BFS는 기본적으로 노드간의 가중치가 1일때만 사용이 가능합니다. 즉, 한 번의 움직임에 모든 노드가 동일한 가중치를 가질때 사용할 수 있다는 뜻입니다. 하지만 이 문제에서는 문을 따냐 따지 못하느냐에 따라 +1과 0의 가중치를 갖습니다. 때문에 queue가 아닌 deque를 사용해 가장 최단거리(=최소한으로 문을 딴 값)를 deque의 맨 앞에 저장할겁니다.
(6) 현 위치의 4방위를 기준으로 for문을 진행합니다.
(7) 만약 이동 가능 범위를 초과했을 경우 continue합니다.
(8) 벽일 경우 마찬가지로 continue 합니다.
(9) 해당 위치의 map의 값이 -1이 아닌 경우, 이미 방문한 지역임을 뜻하며, continue를 하면 됩니다.
(10) 다음 위치가 문이라면 현재 누적 잠금해제 수의 +1을 map에 저장합니다. 그리고 덱의 맨 뒤에 삽입합니다.
(11) 다음 위치가 통로라면(=아직 방문하지 않은 통로), 현재 누적 잠금해제 수를 그대로 저장해주고 덱의 맨 앞에 삽입합니다.
(12) 이렇게 완성한 누적 잠금해제수 map을 반환합니다.
4. 다음은 정답을 출력하는 과정입니다.
for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
if(v[i][j]=='*') continue; // 1
temp = d1[i][j] + d2[i][j] + d3[i][j]; // 2
if(d1[i][j]<0||d2[i][j]<0||d3[i][j]<0) continue; // 3
if(v[i][j]=='#') temp-=2; // 4
if(ans>temp) ans = temp; // 5
}
}
cout << ans << "\n"; // 6(1) 현재 위치가 *이라면 벽이라는 의미이므로, continue 합니다.
(2) 그렇지 않을 경우 문 이거나 빈 통로를 뜻합니다. 상근이와 죄수 2명의 해당 지점에 대한 누적 잠금해제 수를 구합니다.
(3) 만약 세 명의 어느 한명이라도 누적 잠금해제수가 0 미만이라면, 이는 만날 수 없는 지역임을 뜻합니다. continue를 합니다. 이 부분이 이해가 안될경우 로직 4번의 설명을 다시 한 번 확인하시기 바랍니다.
(4) 문일 경우 값을 -2해줍닌다. 이 부분은 로직 2번의 설명과 동일합니다.
(5) 정답값보다 작을 경우, 해당 값을 정답값으로 갱신합니다.
(6) 정답을 출력합니다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int yy,xx,ny,nx,my[]={0,1,0,-1},mx[]={1,0,-1,0};
vector<vector<int>> bfs(vector<vector<char>> &a, int y, int x){
int n = a.size();
int m = a[0].size();
vector<vector<int>> map(n,vector<int>(m));
for(int i=0; i<n; i++){
for(int j=0; j<m; j++) map[i][j] = -1;
}
map[y][x] = 0;
deque<pair<int,int>> q;
q.push_front({y,x});
while(!q.empty()){
yy = q.front().first;
xx = q.front().second;
q.pop_front();
for(int i=0; i<4; i++){
ny = yy+my[i];
nx = xx+mx[i];
if(ny<0||ny>=n||nx<0||nx>=m) continue;
if(a[ny][nx]=='*') continue;
if(map[ny][nx]!=-1) continue;
if(a[ny][nx]=='#'){
map[ny][nx] = map[yy][xx]+1;
q.push_back({ny,nx});
}
else{
map[ny][nx] = map[yy][xx];
q.push_front({ny,nx});
}
}
}
return map;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t;
cin >> t;
while(t--){
int h,w,y1=0,x1=0,y2=0,x2=0,temp=0,ans=1e9;
cin >> h >> w;
vector<vector<char>> v(h+2,vector<char>(w+2));
for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
cin >> v[i][j];
if(v[i][j]=='$'&&y1==0){
y1 = i;
x1 = j;
}
else if(v[i][j]=='$'&&y1!=0){
y2 = i;
x2 = j;
}
}
}
vector<vector<int>> d1 = bfs(v,0,0);
vector<vector<int>> d2 = bfs(v,y1,x1);
vector<vector<int>> d3 = bfs(v,y2,x2);
for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
if(v[i][j]=='*') continue;
temp = d1[i][j] + d2[i][j] + d3[i][j];
if(d1[i][j]<0||d2[i][j]<0||d3[i][j]<0) continue;
if(v[i][j]=='#') temp-=2;
if(ans>temp) ans = temp;
}
}
cout << ans << "\n";
}
return 0;
}
'🖥️ CS > Baekjoon Algorithms' 카테고리의 다른 글
| 백준 17086번 아기 상어 2 (C++) (0) | 2021.06.20 |
|---|---|
| 백준 1600번 말이 되고픈 원숭이 (C++) (0) | 2021.06.17 |
| 백준 2212번 센서 (C++) (0) | 2021.06.14 |
| 백준 1504번 특정한 최단 경로 (C++) (0) | 2021.06.13 |
| 백준 5014번 스타트링크 (C++) (0) | 2021.06.08 |