이번에는 c++로 BFS문제를 풀어보자. 사실 엄청 어렵지는 않은 문제였다. 알고리즘을 어떻게 사용해서 풀지 쉽게 이해할 수 있었다. 그러나 문제는 c++!!!!! 맨날 파이썬으로 풀다가 c++을 접했더니 아주 신경써야할 게 한 두개가 아니다.
괜히 알고리즘 고수들의 언어가 아니었다. 준나 어렵다.
문제는 간단하다. 귀여운 고슴도치가 비버굴로 피난을 가는데 걸리는 시간을 구한다. 단, 물이 넘치게 되는 조건이 있는데 시간이 갈수록 물이 주변 지역으로 퍼진다. 이를 피하며 굴로 이동하면 된다.
가장 빠른 길을 찾는 것이기 때문에 BFS를 선택하면 된다.
또한 고슴도치는 물이 넘치는 지역으로 이동하면 안되기 때문에 물을 먼저 이동시키고 고슴도치를 이동시키면 된다.
1. 땅굴의 위치, 물의 위치, 고슴도치의 위치 파악하여 저장하기
2. BFS 구현 (물부터 이동시키기, 고슴도치의 이동 횟수를 파악 -> 2차원 배열로 만들어 해결했다.)
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
typedef struct item {
int x;
int y;
char z;
}item;
int main() {
char map[51][51] = { '.', };
queue<item> q;
int r, c;
cin >> r >> c; // 행,열
int endx, endy;
item start;
for (auto i = 0; i < r; i++) {
string tmp;
cin >> tmp;
for (auto j = 0; j < c; j++) {
if (tmp[j] == 'D') {
endx = i;
endy = j;
}
else if (tmp[j] == 'S') {
start.x = i;
start.y = j;
start.z = 'S';
}
else if (tmp[j] == '*') {
item tmpitem = { i,j,'*' };
q.push(tmpitem);
}
}
strcpy_s(map[i], tmp.c_str());
}
q.push(start);
//BFS
int dx[4] = { 0,0,1,-1 }; //동서남북
int dy[4] = { 1,-1,0,0 };
int vmap[51][51] = { 0, };
vmap[start.x][start.y] = 1;
while (q.size() != 0) {
item target = q.front();
q.pop();
if (target.x == endx && target.y == endy) {//탈출성공
break;
}
for (int i = 0; i < 4; i++) {
int nx = target.x + dx[i];
int ny = target.y + dy[i];
if (0 <= nx && nx < r && 0 <= ny && ny < c) {//인덱스 범위확인
if (target.z == '*') {//물인경우
if (map[nx][ny] == '.' || map[nx][ny] == 'S') {
map[nx][ny] = '*';
q.push({ nx,ny,'*' });
}
}
else {//고슴도치인 경우
if (map[nx][ny] == '.' || map[nx][ny] == 'D') {
if (vmap[nx][ny] == 0) {
vmap[nx][ny] = vmap[target.x][target.y] + 1;
q.push({ nx,ny,'S' });
}
}
}
}
}
}
if (vmap[endx][endy] == 0) {
printf("KAKTUS\n");
}
else {
cout << vmap[endx][endy] - 1 << endl;
}
}
c++을 거의 몇년만에 쓰다보니 상당히 어색했다. 알고리즘은 이해해도 구현에 상당히 오랜시간이 걸렸다. 빨리 남은것도 복습해야지....
이번에 얻은 팁:
문자열을 저장할때는 null값까지 받다보니 배열크기를 1 늘려주어야 한다.
strcpy_s는 백준에서 안되기 때문에 strcpy를 사용한다.
vector같은걸 쓸때 2개 인자까지만 되므로 3개 부터는 구조체를 만들어 사용한다.
'알고리즘' 카테고리의 다른 글
[c++] 백준 14476 (최대공약수 하나빼기, 누적합, 최대공약수, 유클리드 호제법) (0) | 2021.07.22 |
---|---|
백준 1202 보석도둑 c++ 풀이 (priority queue, vector, 우선순위 큐) (0) | 2021.07.21 |
백준 10026 파이썬 풀이 (적록색약, DFS) (0) | 2021.07.17 |
백준 2583 파이썬 풀이 (영역 구하기, DFS) (0) | 2021.07.17 |
백준 1987 파이썬 풀이 (알파벳, DFS) (0) | 2021.07.17 |