미로 탐색

문졔: 미로 탐색 (백준 2178번)

구조 분석

도착지까지의 최소 칸 수를 세는 문제이므로 전형적인 BFS 문제이다. 해당 좌표와 탐색 depth를 저장하기 위해서 pair<pair<int,int>,int>형태로 노드를 저장해야 한다.

풀이 방법

BFS는 queue를 이용하여 풀면 된다.

코드

#include <stdio.h>
#include <iostream>
#include <string>
#include <queue>
using namespace std;

int n, m, c;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int map[100][100] = {0,};
int visited[100][100] = {0,};

int main() {
    cin >> n >> m;
    string input;
    for (int i=0; i<n; i++) {
        cin >> input;
        for (int j=0; j<m; j++) {
            if (input[j] == '1') {
                map[i][j] = 1;
            }
        }
    }
    queue<pair<pair<int,int>,int>> Q;
    Q.push(make_pair(make_pair(0,0),0));
    while(!Q.empty()) {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int cnt = Q.front().second;
        cnt++;
        Q.pop();
        
        if (x==n-1 && y==m-1) {
            c = cnt;
            break;
        }
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0<=nx && nx<n && 0<=ny && ny<m) {
                if (map[nx][ny]==1 && visited[nx][ny]==0) {
                    visited[nx][ny] = 1;
                    Q.push(make_pair(make_pair(nx,ny),cnt));
                }
            }
        }
    }
    cout << c << "\n";
    return 0;
}

정리

처음에 메모리 초과가 나와서 당황했다. 아래 코드를 참고해서 앞으로 BFS를 설계할 떄 참고하자.

(메모리 초과가 나온 코드)

queue<pair<pair<int,int>,int>> Q;
    Q.push(make_pair(make_pair(0,0),0));
    while(!Q.empty()) {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int cnt = Q.front().second;
        cnt++;
        visited[x][y] = 1;
        Q.pop();
        if (x==n-1 && y==m-1) {
            c = cnt;
            break;
        }
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0<=nx && nx<n && 0<=ny && ny<m) {
                if (map[nx][ny]==1 && visited[nx][ny]==0) {
                    Q.push(make_pair(make_pair(nx,ny),cnt));
                }
            }
        }
    }

(정답 코드)

queue<pair<pair<int,int>,int>> Q;
    Q.push(make_pair(make_pair(0,0),0));
    while(!Q.empty()) {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int cnt = Q.front().second;
        cnt++;
        Q.pop();
        
        if (x==n-1 && y==m-1) {
            c = cnt;
            break;
        }
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0<=nx && nx<n && 0<=ny && ny<m) {
                if (map[nx][ny]==1 && visited[nx][ny]==0) {
                    visited[nx][ny] = 1;
                    Q.push(make_pair(make_pair(nx,ny),cnt));
                }
            }
        }
    }  

pop할때 visted를 check하지 말고, next를 queue에 넣을 때 visited를 check하자.