[Unsolved][C++] 백준 2178 미로 탐색

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

2178번: 미로 탐색

 

1. 서론

 

말 그대로 미로를 탐색하는 문제이다. 최단 거리를 구하는 문제인데 원래 최단 거리 구하는 건 BFS로 풀어야 하는데 아무 생각 없이 DFS로 풀다가 멸망했다는,, 소식

 

2. 문제 풀이

 

N x M 배열이 주어진다. 갈 수 있는 길은 1 아닌 길은 0으로 값이 주어진다. 이때 N, M의 좌표까지 가는 최단거리로 몇 칸을 거쳐야 도착할 수 있는지를 구하는 문제이다. 

 

문제 자체는 심플한데 내가 모자라서 그런지 DFS로 구현하는 것도 꽤 시간이 걸렸다. 근데 나는 맞다고 생각했는데 자꾸 예제 2개 맞으면 2개가 안 맞고 그래서 뭐가 문제지 하고 이때부터 인터넷을 찾아봤다.

 

그 결과 백트래킹을 넣어야 제대로 된 경로를 구할 수 있는 문제였다. 그런데 문제는 백트래킹을 넣으면 제대로 나오긴 하는데 각각 범위가 100 x 100인지라 경우의 수가 너무 많아서 메모리 초과가 나오게 되는 게 문제였다. 결국엔 DFS로는 못 풀고 BFS로 풀어야 답이 제대로 나오는 문제였던 것이다. 나랑 와중에 같은 스텝을 밟은 블로그를 찾게 되어서 결국 이 블로그를 보고 따라 했다.

 

https://cocoon1787.tistory.com/115

[C/C++] 백준 2178번 미로탐색 (BFS, DFS)

 

DFS 코드도 백트래킹 안 한 부분만 빼면 똑같고 BFS인데 처음에 DFS로 풀었다가 망한 과정까지 정말 똑같은... 사람들 생각은 다 비슷한가 보다. (물론 이 분은 결국 혼자 힘으로 BFS로 풀었지만)

 

아 그리고 내가 처음 DFS이면 안되는구나 눈치챈 건 이 글을 보고 나서이다.

 

https://www.acmicpc.net/board/view/85259

글 읽기 - 파이썬) 시작하자마자 틀렸습니다

 

처음에 나는 cnt를 할 때 ++cnt로 값을 넘겼는데 그러다 보니 잘못된 길로 가도 이미 값이 더해져서 넘어가는 문제가 생겼다.

그래서 값을 cnt + 1로 넘기니까 그 문제가 사라지고 모든 예제가 풀렸는데 야심 차게 제출했더니 틀렸습니다가 바로 나와서 황당... 반례를 찾다가 이 글을 발견했고 나도 이 반례가 똑같이 18이 아닌 22가 나왔다. 그래서 그때부터 구글링으로 뭐가 문제지 뒤지다가 백 트래킹하고 메모리 초과 나서 BFS로 돌렸다는,,, ㅎ

 

근데 DFS는 그래도 몇 문제 풀어봤다고 + 재귀라고 좀 익숙한데 BFS는 큐 쓰는 거 + 별로 안 해봐서 낯설어서 어떻게 해야 하는지 감이 잘 안 오더라는,, 문제를 더 많이 풀어야겠지 뭐!! 에휴!

 

3. 코드 설명

 

#include <queue>
#include <iostream>

using namespace std;

int board[101][101], visit[101][101], check[101][101], n, m, ans = 0;
int dx[] = {0, 1, -1, 0}, dy[] = {1, 0, 0, -1};

void bfs(int x, int y)
{
    visit[x][y] = true;
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));

    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && board[a][b] == 1 && !visit[a][b])
            {
                check[a][b] = check[x][y] + 1;
                q.push(make_pair(a, b));
                visit[a][b] = true;
            }
        }
    }
}

int main()
{
    int i, j;
    string s;

    cin >> n >> m;

    for (i = 0; i < n; i++)
    {
        cin >> s;

        for (j = 0; j < m; j++)
            board[i][j] = s[j] - '0';
    }

    bfs(0, 0);
    cout << check[n - 1][m - 1] + 1 << endl;
}

 

값이 붙어서 들어오기 때문에 분리해서 배열에 넣어주는 작업을 해준다.

그리고 bfs를 돌리는데 큐에 첫 번째 좌표의 값을 넣는다. 그리고 반복문을 돌면서 큐가 빌 때, 즉 종료 조건에 다달을 때까지 반복한다.(마지막 좌표에 가면 조건에 걸려서 더 이상 돌 수 없음)

현재 위치에서 상하좌우 좌표가 1인지 아닌지 보고, 방문한 적이 없으면 큐에 넣는다. 큐에 넣는다는 건 그 좌표에 방문하겠단 뜻이므로 방문했다는 표시도 해준다. 그리고 이 문제에서 처음 써봤는데 원래의 미로 배열(board), 그리고 방문 체크 표시 배열(visit) 이외에도 이동 거리를 저장할 수 있는 배열(check)도 만들어서 써봤다. 일종의... 메모인가? 쨌든 각 좌표에 시작 지점으로부터 여기까지 얼마나 걸려서 왔는지를 저장할 수 있다. 그렇게 미로 배열을 다 돌고 나면 도착 지점에 적힌 거리 + 자기 자신 값을 해서 답을 구할 수 있는 것이다.

 

배움에는 정말 끝이 없군아 ㅎ