[C++][백준 2178] 미로탐색 - BFS를 이용한 최단거리

[백준 2178] 미로탐색

문제를 읽고 어떤 알고리즘을 써야하는지 힌트를 얻어보자.

내가 구해야하는 것은,

(1, 1)에서 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수 => BFS!!

 

참고) BFS : 너비 우선 탐색 (Breadth-Frist Search)

1. What? : 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
2. When use? : 두 노드 사이의 최단 경로 or 임의의 경로를 찾을 때 사용한다.
3. How? : 큐(Queue), 노드 방문 여부(isVisited[idx]) 이용

✏️ 그래프 탐색 DFS, BFS 기본 구현을 복습은 아래 링크에서
[C++] DFS와 BFS 구현하기

---

TIP. 어떤 자료구조를 사용하여 데이터를 관리할지 먼저 생각하자.

 

1. Queue : 방문할 수 있는 인접 칸을 Queue에 넣는다.

2. isVisited[i][j] : 방문 여부를 2차원 배열로 관리

3. Edge 구조체 : 칸의 정보를 보다 직관적으로 표현하여 가독성을 높이자.

 

#include <stdio.h>
#include <queue>

using namespace std;

struct Edge {
    int x, y, cost;
    
    Edge(int _x, int _y, int _cost) {
        x = _x;
        y = _y;
        cost = _cost;
    }
};

int N, M;
int map[101][101] = {0, }; // 미로 행렬
int isVisited[101][101] = {false, };
queue<Edge> que;

int posX[4] = {-1, 0, 1, 0}; // 왼쪽, 위, 오른쪽, 아래
int posY[4] = {0, 1, 0, -1}; // 왼쪽, 위, 오른쪽, 아래

bool isInside(int x, int y) {
    return (x >= 1) && (x <= N) && (y >= 1) && (y <= M);
}

int bfs(int X, int Y) {
    que.push(Edge(X, Y, map[X][Y])); // 시작 위치 push
    
    while (!que.empty()) {
        Edge cur = que.front();
        que.pop();
        
        if (isVisited[cur.x][cur.y]) { continue; }
        isVisited[cur.x][cur.y] = true;
        
        if (cur.x == N && cur.y == M) { return cur.cost; } // 종료조건
        
        for (int i=0; i<4; i++) { // 왼쪽, 위, 오른쪽, 아래로 갈 수 있는지 조사
            int nextX = cur.x + posX[i];
            int nextY = cur.y + posY[i];
            
            if (isInside(nextX, nextY) == false) { continue; } // map 영역을 벗어나면 pass
            if (map[nextX][nextY] == 0) { continue; } // 이동 불가하면 pass
            que.push(Edge(nextX, nextY, cur.cost + 1)); // 이동 가능한 칸 정보(Edge)를 que에 넣는다
        }
    }
    
    return 0;
}

int main() {
    
    scanf("%d %d", &N, &M);
    
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    
    int length = bfs(1, 1);
    printf("%d", length);
    
    return 0;
}