2178번 - 미로 탐색(c++)

🗒 2178번 문제

📌 BFS(너비 우선 탐색)으로 구현한 문제(dfs도 당연 가능) ❗️

1️⃣ BFS는 queue를 사용해서 문제 해결!

2️⃣ 출발 위치는 0, 0 으로 설정하고 문제를 풀자!

3️⃣ dx, dy 배열을 사용해서 4방향 탐색을 하자.

4️⃣ 출발점에서 시작하여 BFS는 해당노드에서 상하좌우를 살폈을때 조건
1.지도를 벗어나지 않고, 2.이동할 수 있는 칸이면서, 3.아직 방문하지 않았다면

5️⃣ 만족하면 그 자식노드들을 큐에 담아 또 그 자식노드의 상하좌우를 살펴 조건을 만족하는지 살피게 되는 형태로 탐색을 진행

➰ 코드로 나타낸 2178번 ➰

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int row, col;
int maze[100][100] = { 0 };
int cnt[100][100] = { 0 };
bool entered[100][100];

// 우, 하, 좌, 상
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

void bfs(int x, int y) {
    entered[x][y] = true;
    cnt[x][y]++;
    
    queue<pair<int, int>> q;
    q.push({x, y});
    while(!q.empty()) {
        int n = q.front().first;
        int m = q.front().second;
        // 큐의 현재 원소를 꺼내기
        q.pop();
        
        // 해당 주변 위치를 확인하자
        for (int i = 0; i < 4; i++) {
            int nx = n + dx[i];
            int ny = m + dy[i];
            
            // maze 범위를 벗어나지 않았고 이동할 수 있고 아직 방문하지 않았다면
            if(nx >= 0 && nx < row && ny >= 0 && ny < col && !entered[nx][ny] && maze[nx][ny] == 1) {
            	// 방문하자. 
                entered[nx][ny] = true;
                q.push({nx, ny});
                cnt[nx][ny] = cnt[n][m] + 1;
            }
        }
    }
}

int main() {
    cin >> row >> col;
    
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            scanf("%1d", &maze[i][j]);
        }
    }
    
    bfs(0, 0);
    
    cout << cnt[row-1][col-1] << endl;
    
    return 0;
}