[c++]백준 2178 - 미로 탐색(BFS)

0. [c++] 백준

https://www.acmicpc.net/problem/2178

1. 풀이

1) 음... 하면서 데이터 초과가 발생했었는데, 이 문제는 queue에 중복된 데이터가 계속 쌓이는 문제가 있었어서 그런 것 같다.

visited를 체크하는 위치를 BFS처음 부분에서 queue에 집어넣은 직후로 바꾸어 코드를 수정하니 문제를 해결 할 수 있었다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#include<iostream> #include<vector> #include<string> #include<queue>   using namespace std;   int Y, X; int dirY[4] = { 0,0,1,-1 }; int dirX[4] = { 1,-1,0,0 }; vector<string> maze; queue<pair<int, int> > findHere; bool visited[101][101]; int mazeDay[101][101];     void BFS(int hereY, int hereX) {     for (int i = 0; i < 4; i++) {         int nextY = hereY + dirY[i], nextX = hereX + dirX[i];         if (nextY >= 0 && nextY < Y&&nextX >= 0 && nextX < X)             if (!visited[nextY][nextX] && maze[nextY][nextX] == '1') {                 findHere.push({ nextY, nextX });                 visited[nextY][nextX] = true;                 mazeDay[nextY][nextX] = mazeDay[hereY][hereX] + 1;             }     } }   int main() {     cin >> Y >> X;     string temp;     for (int y = 0; y < Y; y++) {         cin >> temp;         maze.push_back(temp);     }       //초기 설정     findHere.push({ 0,0 });     mazeDay[0][0] = 1;     visited[0][0] = true;          while (!findHere.empty()) {         BFS(findHere.front().first, findHere.front().second);         findHere.pop();     }         cout << mazeDay[Y-1][X-1];   } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!