백준(BOJ) 그래프 순회 - 미로 탐색 (2178) - Silver 1

 

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

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

문제해결

해당 문제가 주어졌을 때 그래프순회를 생각하였고 그 중 최소의 칸 수라는 걸 보고나서 가중치가 없는 그래프에서의 최단경로 알고리즘인 BFS를 이용하여 문제를 해결하면 되겠다라고 생각하였다. BFS는 노드를 탐색할 때 레벨 순서로 탐색하기 때문에 시작 노드로부터 거리가 가까운 노드부터 탐색이 된다. 이로 인해 목표 노드까지의 최단 경로를 탐색할 수 있다. 여기서 중요한건 여태까지 풀었던 그래프 순회와는 다르게 최단경로를 저장 할 distance 배열이 추가적으로 필요하다는 것이다.

 

- Distance 배열: 이 배열은 시작 노드로부터 각 노드까지의 최단 거리를 저장하는 배열이다. 시작 노드로부터 각 노드까지의 거리가 얼마나 되는지를 기록한다. 초기에는 모든 노드에 대한  값만 가지며, BFS 진행 중에 노드를 방문할 때마다 해당 노드의 거리 값을 업데이트합니다

 

1. 미로와 같은 형태의 distance map 생성 후 시작 시작 포인트 거리 저장

• distance가 0이라는건 방문을 하지 않았다라고 볼 수 있다. 따라서 따로 방문 배열을 추가하지 않아도 된다.

vector<vector<ll> >dis(N, vector<ll>(M, 0)); // 최단경로를 저장할 distance 2차원 배열
dis[0][0] = 1; // start point

2. 이후 일반적인 그래프 순회와 같은 방법으로 bfs

• BFS는 큐를 이용하여 그래프를 순회
• 미로의 범위내에 있으며 방문을 한적이 없고 벽이 아닌경우 distance map을 이전 distance값에서 +1하여 1칸 이동 

if(indexCheck(maze, newPoint) == true and visitCheck(dis, newPoint) == false and
	isWall(maze[newPoint.y][newPoint.x] == false)){
	// 최단거리를 확인하기 위해 이전에 움직였던 oldPoint distanse에서 1을 증가 후 queue에 새롭게 삽입
	dis[newPoint.y][newPoint.x] = dis[oldPoint.y][oldPoint.x] + 1; 
	q.push_back(newPoint);
}

• 만약 예시에서 위와 같은 과정을 1회 하면 distance map에서 이동가능한 곳의 최단경로 거리가 갱신되는걸 확인할 수 있다.

• 모든 그래프 순회가 끝났을 경우 distance map

3. 그래프 순회가 끝나면 미로의 각각의 포인트에서의 최단거리가 저장된다. 문제에서항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다. 라고 했기 때문에 여기서 제일 마지막인 N x M의 저장된 값인 15을 출력해주면 된다.

 

전체코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

typedef struct point{
    ll x;
    ll y;
}point;

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

bool indexCheck(vector<vector<ll> >&maze, point p){ // 미로 범위 밖을 벗어나지는 확인
    if(p.x < 0 or p.x >= maze[0].size())
        return false;
    if(p.y < 0 or p.y >= maze.size())
        return false;
    return true;
}

bool visitCheck(vector<vector<ll> >&dis, point p) // 미로에 해당 좌표를 방문한적이 있는지 확인
{
    if(dis[p.y][p.x] == 0 )
        return false;
    return true;
}

bool isWall(ll n){ // 벽인지 아닌지 확인
    if (n == 1)
        return false;
    return true;
}

void bfs(vector<vector<ll> >&maze, vector<vector<ll> >&dis, vector<point>&q)
{
    while(!q.empty()){
        point newPoint;
        point oldPoint;
        oldPoint = q.front(); // 현재 큐에 있는 원소를 뺀 후 oldpoint에 저장
        q.erase(q.begin()); // queue pop

        for(ll i=0; i<4; i++){ // 4방향 탐색
            newPoint.x = oldPoint.x + dx[i];
            newPoint.y = oldPoint.y + dy[i];
            // 미로범위내에 있으며 방문한적이 없고 벽이 아닌경우
            if(indexCheck(maze, newPoint) == true and visitCheck(dis, newPoint) == false and
                isWall(maze[newPoint.y][newPoint.x] == false)){
                    // 최단거리를 확인하기 위해 이전에 움직였던 oldPoint distanse에서 1을 증가 후 queue에 새롭게 삽입
                    dis[newPoint.y][newPoint.x] = dis[oldPoint.y][oldPoint.x] + 1; 
                    q.push_back(newPoint);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r" ,stdin);

    ll N, M;
    string str;
    cin >> N >> M;
    vector<vector<ll> >maze(N, vector<ll>(M, 0)); 
    vector<vector<ll> >dis(N, vector<ll>(M, 0)); // 최단경로를 저장할 distance 2차원 배열
    dis[0][0] = 1; // start point

    for(ll i=0; i<N; i++){
        cin >> str;
        for(ll j=0; j<M; j++){
            maze[i][j] = str[j] - 48;
        }
    }

    vector<point>q;
    point p;
    p.x = 0; p.y = 0; 
    q.push_back(p); // 최초 start point 삽입
    bfs(maze, dis, q);

    cout << dis[N-1][M-1] << "\n";
    // index 시작은 0부터 이므로 -1

    return 0;
}