[ C++ / BFS ] 백준 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

[ Input ]

4 6
101111
101010
101011
111011

[ Output ]

15

📌 예제 2

[ Input ]

4 6
110110
110110
111111
111101

[ Output ]

9

📌 예제 3

[ Input ]

2 25
1011101110111011101110111
1110111011101110111011101

[ Output ]

38

📌 예제 4

[ Input ]

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

[ Output ]

13

---

📝 풀이

핵심

• BFS를 통한 목표 지점까지 최소값을 물어보는 문제!

📌 문자열로 들어오는 미로를 숫자로 바꿔 배열(또는 vector)에 넣어 준다.

• vecMaze[i][j] = strNumber[j - 1] - '0';

📌 이미 방문한 정점은 다시 방문 할 필요 없으므로 각 정점의 방문 상태를 나타내는 방문 배열을 만들어 준다.

📌 깊이를 기록할 깊이 배열을 하나 더 만들어 준다.

📌 BFS 함수 구현

• queue 이용
• 상, 하, 좌, 우 순서로 깊이 기록 밑 queue에 push!

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int iN = 0;
int iM = 0;

vector<vector<int>> vecMaze;
vector<vector<int>> vecDepth;
vector<vector<bool>> vecVisited;
queue<pair<int, int>> q;

int iAnswer = 0;

void BFS(int iRow, int iColumn)
{
    q.pop();

    if (true == vecVisited[iRow][iColumn])
        return;

    vecVisited[iRow][iColumn] = true;

    pair<int, int> Up = { iRow - 1,  iColumn };
    pair<int, int> Down = { iRow + 1,  iColumn };
    pair<int, int> Left = { iRow,  iColumn - 1 };
    pair<int, int> Right = { iRow,  iColumn + 1 };

    if (1 < iRow && false == vecVisited[Up.first][Up.second] && 1 == vecMaze[Up.first][Up.second])
    {
        vecDepth[Up.first][Up.second] = vecDepth[iRow][iColumn] + 1;
        q.emplace(Up);
    }

    if (iN > iRow && false == vecVisited[Down.first][Down.second] && 1 == vecMaze[Down.first][Down.second])
    {
        vecDepth[Down.first][Down.second] = vecDepth[iRow][iColumn] + 1;
        q.emplace(Down);
    }

    if (1 < iColumn && false == vecVisited[Left.first][Left.second] && 1 == vecMaze[Left.first][Left.second])
    {
        vecDepth[Left.first][Left.second] = vecDepth[iRow][iColumn] + 1;
        q.emplace(Left);
    }

    if (iM > iColumn && false == vecVisited[Right.first][Right.second] && 1 == vecMaze[Right.first][Right.second])
    {
        vecDepth[Right.first][Right.second] = vecDepth[iRow][iColumn] + 1;
        q.emplace(Right);
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> iN >> iM;

    vecMaze.resize(iN + 1);
    vecDepth.resize(iN + 1);
    vecVisited.resize(iN + 1);

    string strNumber = "";

    for (int i = 1; i <= iN; ++i)
    {
        vecMaze[i].resize(iM + 1);
        vecDepth[i] = vector<int>(iM + 1, 0);
        vecVisited[i] = vector<bool>(iM + 1, false);

        cin >> strNumber;

        for (int j = 1; j <= strNumber.length(); ++j)
        {
            vecMaze[i][j] = strNumber[j - 1] - '0';
        }
    }

    q.emplace(1, 1);
    vecDepth[1][1] = 1;

    while (false == q.empty())
    {
        BFS(q.front().first, q.front().second);
    }

    cout << vecDepth[iN][iM];

    return 0;
}

---

༼ つ ◕_◕ ༽つ 여담

😥 결국은 손으로 그림 그리면서 품...
분명 내 함수는 이상이 없는데 자꾸 이상한 값을 내뱉길래 디버깅 하면서 손으로 미로 그려가면서 했는데... 한 중간 쯤 진행 했을 때 for문에 조건식을 잘못 준거 발견..


그리고 if 문이 많다보니 많이 지저분하다....
나중에 코드 압축 되면 줄여봐야지!