https://www.acmicpc.net/problem/3055
3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제
www.acmicpc.net
코드 설명
큐를 2개를 이용하였다. start큐는 이동하는 경로, water 큐는 물의 경로이다.
일반 BFS while()문 내에 각각의 큐를 넣어 반복하였다.
전체 while()문 내에
1. 먼저 물 4방향씩 이동 ( 이동 후 물(*) 찍어주기)
2. 이후 고슴도치 4방향 탐색 이동 ( visited배열 사용했습니다)
3. 하루 증가
과 같이 계속해서 반복해주었습니다.
배운점!!
매번 BFS를 이용하여 끝까지 탐색하는것만 생각했는데 큐의 사이즈를 이용 + 이중while문 활용 하여 한칸씩 이동후 검사하는 방법!
코드
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
char map[51][51];
int R, C;
bool flag;
bool visited[51][51];
beaver target;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
int cnt;
queue<pair<int, int>> start;
queue<pair<int, int>> water;
void BFS() {
while (!start.empty()) { // 전체 while
cnt++; // 날짜하루증가
int w_size = water.size();
while (w_size--) { //물먼저이동
int y = water.front().first;
int x = water.front().second;
water.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
if (map[ny][nx] == '*' || map[ny][nx] == 'X'||map[ny][nx]=='D') continue;
map[ny][nx] = '*'; //맵에 물 표기
water.push({ ny,nx });
}
}
//S이동
int s_size = start.size();
visited[start.front().first][start.front().second] = true;
while (s_size--) {
int y = start.front().first;
int x = start.front().second;
if (map[y][x] == 'D') { //도착
cout << cnt - 1;
flag = true;
}
start.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
if (map[ny][nx] == '*' ||map[ny][nx] == 'X') continue;
if (!visited[ny][nx]) {
visited[ny][nx] = true;
start.push({ ny,nx });
}
}
}
}
if (flag == false) cout << "KAKTUS"; //비버굴 만나지 못한경우
}
int main() {
cin >> R >> C;
for (int y = 0; y < R; y++) {
for (int x = 0; x < C; x++) {
cin >> map[y][x];
if (map[y][x] == 'S') {
start.push({ y,x });
}
else if (map[y][x] == '*') {
water.push({ y,x });
}
}
}
BFS();
return 0;
}'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] DFS와 BFS (1260/C++) (0) | 2021.08.19 |
|---|---|
| [백준] 욕심쟁이 판다 (1937/C++) (0) | 2021.08.17 |
| [백준] 안전영역 (2468/C++) (0) | 2021.08.06 |
| [백준] 상어 초등학교(21608번/C++) (0) | 2021.06.05 |
| [백준] 마법사 상어와 비바라기(21610 /C++) (0) | 2021.06.04 |
