[백준 2178, c++] 미로탐색(bfs)

문제 번호

• 2178(https://www.acmicpc.net/problem/2178)

문제 및 입/출력

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

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

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

 

입력

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

 

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

예제 입력1

4 6 101111 101010 101011 111011

예제 출력1

15

예제 입력2

4 6 110110 110110 111111 111101

예제 출력2

9

예제 입력3

2 25 1011101110111011101110111 1110111011101110111011101

예제 출력3

38

예제 입력4

7 7 1011111 1110001 1000001 1000001 1000001 1000001 1111111

예제 출력4

13

 

문제 풀이

미로에서 0,0 부터 n,m까지 최단거리를 구하는 문제, bfs를 통해 풀 수 있다.

- 4방향 탐색 필요

- 입력이 붙어서 주어진다.(ex> 1101010)

- 최단거리 탐색

 

소스코드 상에 주석으로 자세한 설명을 적어놓았지만, 다시한번 설명하겠다.

 

0. 미로의 크기를 입력받는다.

1. 우선 배열을 통해 그래프 정보를 입력받는다.

2. 그래프를 BFS 알고리즘을 통해 탐색을 진행한다.

디버깅을 통해 이해를 도왔다. 아래는 예제 1번을 아래와 같은 printf를 집어넣어 디버깅했을때 결과를 해석한 것이다.

3. 최단거리를 출력

 

* 예제를 통한 설명(예제 1번)

예제 입력1

4 6  101111  101010  101011  111011

예제 출력1

15

출발점에서 시작하여 BFS는 해당노드에서 상하좌우를 살폈을때 조건(1.지도를 벗어나지 않고, 2.이동할 수 있는 칸이면서, 3.아직 방문하지 않았다면)을 만족한다면 그 자식노드들을 큐에 담아 또 그 자식노드의 상하좌우를 살펴 조건을 만족하는지 살피게 되는 형태로 탐색을 진행한다.

이 예제에서 주의깊게 봐야할 부분은 위 그림의 (y,x -> 0,4)인 노드와 (y,x -> 2,4)인 노드이다. 이 외의 노드들은 왔던점을 제외하고, 상하좌우에 갈 수 있는곳이 하나 밖에 없지만 해당 노드들은 2개 이상의 갈 수 있는 곳이 존재한다.

 

dist[ny][nx] = dist[y][x] + 1; // 이전 방문값 + 1  (다음 노드 방문값 = 이전노드 방문값 + 1)

 

이므로, (y,x -> 0,4) 에서 갈 수 있는 노드인 (ny,nx -> 0,5) 와 (ny,nx -> 1,4)는 각각 12라는 동일한 dist값을 갖는다.

(ny,nx -> 0,5) 노드에서는 더이상 상하좌우에 갈곳이 없기때문에 진행이 종료되고, (ny,nx -> 1,4)노드에서는 이어서 진행하게 된다.

 

(y,x -> 2,4)에서도 갈 수 있는 노드인  (ny,nx -> 2,5) 와 (ny,nx -> 3,4)는  각각 14라는 동일한 dist 값을 갖게되고, 

(ny,nx -> 2,5) 에서 상하좌우 조건 체크후 마지막 노드에 방문하게 되고, (ny,nx -> 3,4) 는 상하좌우 조건 체크시 마지막 노드에 이미 방문했으므로 그대로 종료한다.

 

---

예제 입력4

7 7  1011111  1110001  1000001  1000001  1000001  1000001  1111111

예제 출력4

13

 

추가로 예제 4도 출력을 나타내 진행상황을 한번 봐보았다. 

예제 4의 경우에는 y,x->1,0 노드에서 갈라지는 것을 볼 수 있는데, 결과를 보면 쉽게 이해 가능하다. 

 

(y,x->1,0) 노드에서 자식노드가 (y,x->1,1)과 (y,x->2,0)으로 갈라져서 목적지까지 동시에 탐색하게 된다.

둘중에 (y,x->2,0)쪽으로 뻗은 자식노드가 13번만에 목적지에 도달하게 되고, (y,x->1,1)로 뻗은 자식노드는 15번만에 도달하게되지만 도착지점에서 이미 빨리 도착한 자식노드가 방문을 했으므로 목적지 노드의 dist는 13이 된다.

 

소스 코드

#include <iostream>
#include <queue> // use bfs algorithm
#include <stdio.h> // use printf, scanf
#include <cstring> // use memset
 
#define MAX_SIZE 100
 
using namespace std;
 
int N, M;
int graph[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
int dist[MAX_SIZE][MAX_SIZE];
 
// 우,하,좌,상
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0 , -1 };
 
bool IsInside(int ny, int nx) {
    return (0 <= nx && 0 <= ny && nx < M && ny < N);
}
 
void bfs(int y, int x) {
    queue< pair<int, int> > q; // 이용할 큐, (y,x)
    // 처음 y,x를 방문 했기 때문에
    visited[y][x] = true;
    dist[y][x] = 1;
 
    q.push(make_pair(y, x));
    while (!q.empty()) {
        // 큐의 현재 원소를 꺼내기
        y = q.front().first;
        x = q.front().second;
        q.pop();
 
        // 해당 위치의 주변을 확인
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            // 지도를 벗어나지 않고, 이동할 수 있는 칸이면서, 아직 방문하지 않았다면
            if (IsInside(ny,nx) && graph[ny][nx] && !visited[ny][nx]) {
                visited[ny][nx] = true;
                dist[ny][nx] = dist[y][x] + 1; // 이전 방문값 + 1
                q.push(make_pair(ny, nx));
            }
        }
    }
}
 
int main() {
    /* 그래프 및 방문기록, 거리 초기화 */
    memset(graph, false, sizeof(graph));
    memset(visited, false, sizeof(visited));
    memset(dist, false, sizeof(dist));
 
    /* 미로(그래프)의 크기 입력*/
    scanf("%d %d", &N, &M);
 
    /* 그래프 정보 입력 */
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%1d", &graph[i][j]);
        }
    }
 
    /* 그래프를 BFS를 통해 탐색 */
    bfs(0, 0);
 
    /* 최소 블럭 개수를 출력 */
    printf("%d\n", dist[N-1][M-1]);
    return 0;
}