궤도
[백준] 3055번 : 탈출 본문
문제
풀이
이 문제를 풀고나서 다른 사람들의 소스코드를 몇 개 봤다.
근데 다들 큐를 2개 사용하거나, while문을 두번 돌리거나 하는 식으로 홍수의 확산과 고슴도치의 이동을 따로따로 관리하는 방법으로 코드를 작성하는 듯 했다. 근데 굳이 그럴 필요 없다.
고슴도치가 없어서 내가 좋아하는 호랑이로 대체했다.
아무튼 이렇게 홍수와 고슴도치의 초기 상태가 주어졌다고 하자.
큐에 홍수의 위치 정보를 먼저 넣고 고슴도치의 위치 정보를 넣었다.
큐의 맨 앞에 있는 파도가 빠지고 새로운 파도의 위치 정보가 큐에 삽입된다.
이런식으로 하면 큐 하나로 홍수와 고슴도치를 관리할 수 있다.
한편,
이렇게 이전에 고슴도치가 방문한 곳이 홍수에 잠길 수도 있다.
그렇기 때문에 고슴도치의 visited는 다른 배열에 저장해서 관리해야 한다.
홍수의 visited와 고슴도치의 visited만 분리하면 하나의 큐와 하나의 while문으로 문제를 해결할 수 있다.
소스코드
#include <iostream>
#include <string>
#include <queue>
#include <utility>
using namespace std;
int R, C;
char map[50][50]; //지도
int dist[50][50]; //고슴도치의 이동
pair<int, int> dir[4] = {{-1, 0}, //상
{1, 0}, //하
{0, -1}, //좌
{0, 1}}; //우
int bfs(pair<int, int> start, pair<int, int> end, vector<pair<int, int>> water) {
queue<pair<int, int>> q;
for (int i = 0; i < water.size(); i++) //물 정보 먼저 넣고
q.push(water[i]);
q.push(start); //고슴도치 정보 투입
dist[start.first][start.second] = 1; //시작점 visited 체크
while (!q.empty()) {
int row = q.front().first;
int col = q.front().second;
if (dist[end.first][end.second]) //도착점의 dist 값이 0이 아니면
return dist[end.first][end.second] - 1;
q.pop();
for (int i = 0; i < 4; i++) {
int nr = row + dir[i].first;
int nc = col + dir[i].second;
if ((nr >= 0) && (nr < R) && (nc >= 0) && (nc < C)) { //범위 확인
if ((dist[row][col] != 0) && (dist[nr][nc] == 0) &&
((map[nr][nc] == '.') || (map[nr][nc] == 'D'))) { //고슴도치 이동
dist[nr][nc] = dist[row][col] + 1;
q.push(make_pair(nr, nc));
} else if ((map[row][col] == '*') && (map[nr][nc] == '.')) { //홍수 이동
map[nr][nc] = '*';
q.push(make_pair(nr, nc));
}
}
}
}
return 0;
}
int main() {
string tmp;
pair<int, int> start, end;
vector<pair<int, int>> water;
cin >> R >> C;
for (int i = 0; i < R; i++) {
cin >> tmp;
for (int j = 0; j < C; j++) {
map[i][j] = tmp[j];
if (map[i][j] == 'S') //시작점
start = make_pair(i, j);
else if (map[i][j] == 'D') //도착점
end = make_pair(i, j);
else if (map[i][j] == '*') //홍수
water.push_back(make_pair(i, j));
}
}
int result = bfs(start, end, water);
if (result == 0) //길이 없음
cout << "KAKTUS\n";
else //출력 가능
cout << result;
}전체 소스코드다.
char map[50][50]; //지도
int dist[50][50]; //고슴도치의 이동지도 정보를 저장함과 동시에 홍수의 visited도 갱신할 map 2차원 배열과
고슴도치의 이동 횟수 정보를 저장함과 동시에 visited도 체크할 dist 2차원 배열이다.
int main() {
string tmp;
pair<int, int> start, end;
vector<pair<int, int>> water;
cin >> R >> C;
for (int i = 0; i < R; i++) {
cin >> tmp;
for (int j = 0; j < C; j++) {
map[i][j] = tmp[j];
if (map[i][j] == 'S') //시작점
start = make_pair(i, j);
else if (map[i][j] == 'D') //도착점
end = make_pair(i, j);
else if (map[i][j] == '*') //홍수
water.push_back(make_pair(i, j));
}
}
int result = bfs(start, end, water);
if (result == 0) //길이 없음
cout << "KAKTUS\n";
else //출력 가능
cout << result;
}입력값을 map에 저장하면서 시작점, 도착점, 홍수의 정보를 따로 저장한다.
int bfs(pair<int, int> start, pair<int, int> end, vector<pair<int, int>> water) {
queue<pair<int, int>> q;
for (int i = 0; i < water.size(); i++) //물 정보 먼저 넣고
q.push(water[i]);
q.push(start); //고슴도치 정보 투입
dist[start.first][start.second] = 1; //시작점 visited 체크
while (!q.empty()) {
int row = q.front().first;
int col = q.front().second;
if (dist[end.first][end.second]) //도착점의 dist 값이 0이 아니면
return dist[end.first][end.second] - 1;
q.pop();
for (int i = 0; i < 4; i++) {
int nr = row + dir[i].first;
int nc = col + dir[i].second;
if ((nr >= 0) && (nr < R) && (nc >= 0) && (nc < C)) { //범위 확인
if ((dist[row][col] != 0) && (dist[nr][nc] == 0) &&
((map[nr][nc] == '.') || (map[nr][nc] == 'D'))) { //고슴도치 이동
dist[nr][nc] = dist[row][col] + 1;
q.push(make_pair(nr, nc));
} else if ((map[row][col] == '*') && (map[nr][nc] == '.')) { //홍수 이동
map[nr][nc] = '*';
q.push(make_pair(nr, nc));
}
}
}
}
return 0;
}그리고 bfs 함수를 실행한다.
for (int i = 0; i < water.size(); i++) //물 정보 먼저 넣고
q.push(water[i]);
q.push(start); //고슴도치 정보 투입
dist[start.first][start.second] = 1; //시작점 visited 체크홍수에 잠길 예정인 지역은 고슴도치가 갈 수 없다는 문제의 조건을 충족하고자
홍수의 정보를 먼저 큐에 넣고, 고슴도치의 정보를 넣는다.
고슴도치의 시작점을 visited 처리하기 위해 dist를 1로 설정한다.
int row = q.front().first;
int col = q.front().second;
if (dist[end.first][end.second]) //도착점의 dist 값이 0이 아니면
return dist[end.first][end.second] - 1;
q.pop();도착점의 dist값이 0이 아닐 때, 그니까 visited 처리가 됐을 때 리턴한다.
처음에 0의 거리로 갈 수 있는 S를 1로 초기화 했기 때문에 1을 뺀 값을 리턴한다.
for (int i = 0; i < 4; i++) {
int nr = row + dir[i].first;
int nc = col + dir[i].second;
if ((nr >= 0) && (nr < R) && (nc >= 0) && (nc < C)) { //범위 확인
if ((dist[row][col] != 0) && (dist[nr][nc] == 0) &&
((map[nr][nc] == '.') || (map[nr][nc] == 'D'))) { //고슴도치 이동
dist[nr][nc] = dist[row][col] + 1;
q.push(make_pair(nr, nc));
} else if ((map[row][col] == '*') && (map[nr][nc] == '.')) { //홍수 이동
map[nr][nc] = '*';
q.push(make_pair(nr, nc));
}
}
}그리고 상하좌우 좌표를 확인하는데
if ((dist[row][col] != 0) && (dist[nr][nc] == 0) &&
((map[nr][nc] == '.') || (map[nr][nc] == 'D'))) { //고슴도치 이동
dist[nr][nc] = dist[row][col] + 1;
q.push(make_pair(nr, nc));
}dist[row][col]가 0이 아니란 것은 현재 고슴도치가 이동중이라는 것이다.
또한 dist[nr][nc]이 0이란 뜻은 unvisited라는 것이고, 이 상태에서 map[nr][nc]이 '.'(길)이거나 'D'(도착점)일 때 그 곳으로 이동할 수 있다. 고슴도치가 이동할 때는 dist 정보만 갱신한다.
고슴도치가 이미 지난 곳을 홍수가 지나갈 수도 있기 떄문에 dist[row][col]가 0이 아니어도 홍수일 가능성이 있긴 하다. 그치만 그 곳에서 갈 수 있는 좌표는 이미 고슴도치가 지나갔을 것이기 때문에 dist[nr][nc]이 0이 아닐 것이라 걸러낼 수 있다.
else if ((map[row][col] == '*') && (map[nr][nc] == '.')) { //홍수 이동
map[nr][nc] = '*';
q.push(make_pair(nr, nc));
}홍수는 '*'로 표시되기 떄문에 map[row][col]가 '*'이라면 홍수가 이동중이라는 것이다.
홍수는 길로만 갈 수 있기 때문에 map[nr][nc]이 '.'일 때만 그곳으로 이동할 수 있고, 홍수가 이동할 때는 map 정보만 갱신한다.
