백준 2178: 미로 탐색

📃 문제: 백준 11659(구간합 구하기 5)

2178번: 미로 탐색

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

( 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. )

 

 

🥈 난이도: 실버 1

 

😲 사용한 개념: BFS(너비우선탐색)

DFS(깊이 우선 탐색)	BFS(너비 우선 탐색)
Stack	Queue

 

💡 BFS란?

1️⃣ 탐색 시작 노드 정보를 큐에 삽입하고  pop연산과 동시에 방문처리 한다.
2️⃣ pop한 노드의 인접 노드들 중 방문처리가 되지 않은 노드 정보를 큐에 삽입하고 방문 처리한다.
3️⃣ 인접노드 push가 끝나면, 최상단 노드를 pop하고, 2~3번 과정을 큐가 empty상태가 될 때까지 반복한다.

 

 

📖 풀이 사고 과정

 

 

 

 

👩‍💻 구현 코드(c++ 사용)

#include <iostream>
#include <queue>
using namespace std;

static int dx[] = { 0,1,0,-1 };//상, 우, 하, 좌
static int dy[] = { 1, 0, -1, 0 };//상, 우, 하, 좌
static int A[101][101];
static bool visited[101][101] = { false };
static int N, M;

void BFS(int i, int j) {
    //큐에 시작점(x,y) push
    queue<pair<int, int>> myQueue;
    myQueue.push(make_pair(i, j));

    while (!myQueue.empty()) {
        int now[2];
        now[0] = myQueue.front().first;//x좌표
        now[1] = myQueue.front().second;//y좌표
        myQueue.pop();
        visited[i][j] = true;//pop & 방문처리
        for (int i = 0; i < 4; i++) {
            int x = now[0] + dx[i];//상,하,좌,우 움직였을 때 x값
            int y = now[1] + dy[i];//상,하,좌,우 움직였을 떄 y값
            if (x >= 0 && y >= 0 && x < N && y < M) {
                if (!visited[x][y] && A[x][y] != 0) {
                    myQueue.push(make_pair(x, y));
                    visited[x][y] = true;
                    A[x][y] = A[now[0]][now[1]] + 1;//depth 1 추가
                }
            }
        }
    }

}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> s;
        for (int j = 0; j < M; j++) {
            A[i][j] = s[j] - '0';
        }
    }
    BFS(0, 0);
    cout << A[N - 1][M - 1] << endl;
    return 0;
}