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

문제 링크 : https://boj.kr/2178

지난번에 풀었던 BOJ 7576 토마토 문제보다 훨씬 쉬운 BFS 문제인듯 하다.

토마토 문제에서 잡았던 대부분의 기본 개념을 그대로 가지고 풀었다.

토마토 보다 이 문제를 더 먼저 풀었으면 좋았을걸..

먼저 이 문제는 입력 자료형이 공백으로 구분지어져있지 않기 때문에 

1. std::istringstream 를 split 하여 입력받기

2. char형 그대로 입력 받는 방법

3. 스트링 클래스의 getline(std::cin, input); 사용

4. scanf("%1d", &input); 처럼 형식지정자로 1자리만 받도록 하기

등등 다양한 방법을 활용하여 입력 받아야 한다. 이 외에도 getch나 gets 등등 아주 많다.

scanf를 사용하는게 제일 편하긴 하지만 난 2번의 방법을 이용하여 입력을 받았다. 입력된 자료는 문자로서 '1'과 '0'으로 입력받게 된다.

뭘 사용하던 어짜피 별 차이 없긴 하다.

입력을 받았으면 가장 먼저 큐에 현재 노드를 큐에 bfs.push({1, 1, 1}); 집어넣어 준다.

그리고 반드시 현재 방문 노드 좌표를 maze[1][1] = '0'; 체크 해준다.

그 다음 노드를 상, 하, 좌, 우로 탐색하고 (N, M)을 찾을 때까지 무한 반복한다.

BFS 탐색은 탐색 단계가 동일 선상에서 진행되기 때문에 (N, M)을 가장 먼저 찾았을 때의 cnt 값이 최단 거리가 된다.

N,M을 찾지 못하였다면 다음 노드가 미로에서 이동 가능한 칸이라면 큐에 집어 넣어준다.

이때, 중요한게 있는데 큐에 넣음과 동시에 반드시 maze[nextNode.n][nextNode.m] = '0'; 로 방문 체크를 해줘야한다.

난 처음에 다른 부분에서 방문 체크를 해줬기 때문에 위에서 말한 것처럼 BFS 탐색시에 메모리 초과가 나게 되었다.

// BOJ 2178 미로 탐색
#include <bits/stdc++.h>
 
using namespace std;
const int dir[4][2] = {{1,  0}, {0,  1}, {0,  -1}, {-1, 0}}; // 4방향
char maze[102][102];
 
struct node{
    int n;
    int m;
    int cnt; // 칸 수
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
    int N, M;
    cin >> N >> M;
    queue<node> bfs;
 
    for (int i = 1; i <= N; i++)
        cin >> maze[i] + 1;
 
    bfs.push({1, 1, 1}); // 시작 지점 (1, 1) 1칸
    maze[1][1] = '0';
    int result = 0;
    while(true){
        node curNode = bfs.front();
        bfs.pop();
        // 현재 노드를 기준으로 상,하,좌,우 탐색
        for(int i = 0; i < 4; i++) {
            int nextN = curNode.n + dir[i][0];
            int nextM = curNode.m + dir[i][1];
            // (N, M)을 찾았다면 loop를 빠져나감
            if(nextN == N && nextM == M){
                result = curNode.cnt + 1;
                goto END;
            }
            if(maze[nextN][nextM] == '1') { // 이동할 수 있는 칸이라면
                // 다음 노드의 좌표와 칸 수를 저장시킴
                node nextNode = {nextN, nextM, curNode.cnt + 1};
                // 지나간 경로는 다시 돌아갈 수 없도록 변경
                maze[nextNode.n][nextNode.m] = '0';
                // 큐에 다음 노드 저장
                bfs.push(nextNode);
            }
        }
    }
    END:
    cout << result;
 
    return 0;
}
 
 

메모리 초과가 났던 코드 일부분 (아래 코드의 4번째 줄, 위 코드의 45번째 줄과 비교)

while(true){
    node curNode = bfs.front();
    // 지나간 경로는 다시 돌아갈 수 없도록 변경
    maze[curNode.n][curNode.m] = '0';
    bfs.pop();
    // 현재 노드를 기준으로 상,하,좌,우 탐색
    for(int i = 0; i < 4; i++) {
        int nextN = curNode.n + dir[i][0];
        int nextM = curNode.m + dir[i][1];
        // (N, M)을 찾았다면 loop를 빠져나감
        if(nextN == N && nextM == M){
            result = curNode.cnt + 1;
            goto END;
        }
        if(maze[nextN][nextM] == '1') { // 이동할 수 있는 칸이라면
            // 다음 노드의 좌표와 칸 수를 저장시킴
            node nextNode = {nextN, nextM, curNode.cnt + 1};
            // 큐에 다음 노드 저장
            bfs.push(nextNode);
        }
    }
}