[백준 2178] 미로탐색

백준 2178 미로탐색

이 문제는 (1,1)부터 시작해 (N,M)로 가는 길 중 가장 짧게 갈 수 있는 경로를 찾는 것이다. 

최단 경로를 구하는 문제는 대부분 BFS로 푸는 문제이다. 따라서 이 문제도 BFS로 푸는 문제이다.

BFS는 queue를 이용하는데 queue에서 pop할때 도착 지점의 좌표가 나올때까지 하면 된다.

문제에 길은 무조건 있다고 하니깐 그냥 없을 경우를 생각하지 않고 계속 push하고 pop을 하면 된다.

1. pair가 있다는 걸 몰랐을 때 짠 소스(queue에 대해서 독학 했을 때...)

#include<cstdio>
#include<queue>
 
struct xy
{
    int i;
    int j;
};
 
int input[100][100] = { 0 };
 
std::queue<xy> Q;
 
int main()
{
    int N, M, i ,j;
    scanf("%d %d", &N, &M);
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < M; j++)
        {
            scanf("%1d", &input[i][j]);
        }
    }
 
    Q.push({ 0,0 });
    int qi, qj, qsize;
    int sum = 0;
 
    while (!Q.empty())
    {
        sum++;
        qsize = Q.size();
        while (qsize--) {
            qi = Q.front().i;
            qj = Q.front().j;
            Q.pop();
            if (qi == N - 1 && qj == M - 1)break;
            if (qi >= 1 && input[qi - 1][qj] == 1) {
                input[qi - 1][qj] = 0;
                Q.push({ qi - 1,qj });
            }
            if (qi < N - 1 && input[qi + 1][qj] == 1)
            {
                input[qi + 1][qj] = 0;
                Q.push({ qi + 1,qj });
            }
            if (qj >= 1 && input[qi][qj - 1] == 1)
            {
                input[qi][qj - 1] = 0;
                Q.push({ qi, qj - 1 });
            }
            if (qj < M - 1 && input[qi][qj + 1] == 1)
            {
                input[qi][qj + 1] = 0;
                Q.push({ qi,qj + 1 });
            }
        }
        if (qi == N - 1 && qj == M - 1)break;
    }
    printf("%d", sum);
    return 0;
}

2. 위 소스를 제출하고 2달이 지난 후

#include<cstdio>
#include<queue>
 
using namespace std;
 
queue<pair<int, int>> Q;
 
int map[100][100] = { 0 };
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
int N, M;
 
bool Check(int x, int y)
{
    return (x >= 0 && x < M && y >= 0 && y < N);
}
 
int main()
{
    int i ,j;
    scanf("%d %d", &N, &M);
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < M; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
 
    Q.push(make_pair(0,0));
    int qi, qj, qsize;
    int sum = 0;
 
    while (!Q.empty())
    {
        sum++;
        qsize = Q.size();
        while (qsize--) {
            qi = Q.front().first;
            qj = Q.front().second;
            Q.pop();
            if (qi == N - 1 && qj == M - 1)break;
            for(int k=0;k<4;k++)
            {
                int qx = qj + dx[k];
                int qy = qi + dy[k];
                if(!Check(qx,qy))continue;
                if(map[qy][qx])
                {
                    map[qy][qx] = 0;
                    Q.push(make_pair(qy,qx));
                }
            }
        }
        if (qi == N - 1 && qj == M - 1)break;
    }
    printf("%d", sum);
    return 0;
}