[백준/c++] - 2178 미로 탐색

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

2178번: 미로 탐색

 

 

 

 

 

 

 DFS, BFS, 다익스트라와 같은 최단 경로 탐색 알고리즘을 학습한 후, 복습겸 풀어본 문제이다. 옛날에도 이미 많이 풀었던 문제지만 다시보니 또 새롭다.

 

 

 

 

 

 

 

 

 

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

// 간선에 비용이 동일한(없는) 최단 경로 탐색 -> BFS
// 그래프 표현 방식 -> 인접 행렬 방식, 2차 배열

struct pos {
    int X;
    int Y;
} typedef Pos;


Pos front[4]
{
    Pos{-1, 0}, // Up
    Pos{0, -1}, // Left
    Pos{1, 0}, // Down
    Pos{0, 1}, // Right
};

int main()
{
    int N, M = 0;


    // 입력 -----------------------------
    cin >> N >> M;
    vector<vector<int>> map(N, vector<int>(M, 0));
    vector<vector<int>> discoverd(N, vector<int>(M, 0));
    queue<Pos> bfsQueue;


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

    Pos root{ 0, 0 };
    bfsQueue.push(root);

    while (!bfsQueue.empty())
    {
        // 주변 상하좌우부터 탐색
        Pos cur = bfsQueue.front();
        bfsQueue.pop();


        // 도착인지 확인
        if (cur.X == N - 1 && cur.Y == M - 1) // 도착
        {
            break;
        }


        for (int i = 0; i < 4; i++) // 상하좌우 4
        {
            Pos move = front[i];
            Pos next;

            next.X = cur.X + move.X;
            next.Y = cur.Y + move.Y;

            // 맵을 벗어낫는지 확인
            if (next.Y >= M || next.X >= N || next.Y < 0 || next.X < 0) // 맵을 벗어난 경우
                continue;
            
            // 이미 발견한 지점인지 확인 & 갈 수 있는 지점인지 확인
            if (map[next.X][next.Y] != 1 || discoverd[next.X][next.Y] != 0) 
            {
                continue;
            }
            else
            {
                // 조건에 맞는 지점에 대해 큐에 삽입하여 탐색 예약
                discoverd[next.X][next.Y] = discoverd[cur.X][cur.Y] + 1; // discovered 에는 현재 지점까지 오는데 걸리는 횟수를 기록함
                bfsQueue.push(next);
            }


        }
    }

    cout << discoverd[N - 1][M - 1] + 1 << endl;



    return 0;
}

 

 

 

 

 

 

 

 

 알고리즘은 BFS를 활용하였다. DFS를 활용할 수도 있겠지만 대부분의 미로 문제는 BFS로 푸는 것이 바람직하다고 배웠다. 코드 내용 자체는 기본적인 경로 탐색 문제이기에 특별히 설명할 것이 없다.

 

 

 

 

 

 

 

 

 

 

 

 여유롭게 학습한다는 차원에서 주석까지 달아가며 풀었는데, 오히려 생각 정리가 잘되는 기분이다. 다음에도 문제를 풀 때 적당한 주석은 달아가면서 하는 것이 오히려 시간단축에 도움을 줄지도 모르겠다.