[백준 14940] 쉬운 최단거리

문제

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

 

 

문제 분석

지도의 크기가 우선 정해진다. 

 

갈 수 없는 곳은 0, 갈 수 있는 곳은 1, 시작 위치는 2로 표시 된다. 

 

2에서 시작하여 좌우양옆으로 방문한 순서를 출력해주는 문제이다. 

 

여기서 갈 수 있는 곳 1인 곳인데 갈 수 없는 곳이라면 -1로 출력한다. 

 

 

알고리즘 설계

우선 지도의 크기를 정해서 지도를 그린다. 

 

시작 위치는 따로 관리하며 지도엔 0으로 표시한다. 

 

갈 수 있는 곳은 -1로 표시하여 나중에 1번쨰로 도착한 곳과 헷갈리지 않도록 해준다. 

 

이후 BFS를 사용하여 몇번쨰에 도착하였는지 map에 적어준 후 출력한다. 

 

 

유의점

x축과 y을 착각하지 않고 적는 것이 중요하다. 

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int map[1001][1001];
int moveX[4]{ 1, -1, 0, 0 };
int moveY[4]{ 0, 0, 1, -1 };

int main()
{
    int x, y, input, startX, startY;
    queue<pair<int, int>> q;
    cin >> x >> y;

    for (int i = 0; i < x; ++i)
    {
        for (int j = 0; j < y; ++j)
        {
            cin >> input;
            if (input == 2)
            {
                q.push(make_pair(i, j));
                map[i][j] = 0;
            }
            else if (input == 1)
                map[i][j] = -1;
            else
                map[i][j] = input;
        }
    }

    while (!q.empty())
    {
        int posX = q.front().first;
        int posY = q.front().second;

        for (int i = 0; i < 4; ++i)
        {
            int addX = posX + moveX[i];
            int addY = posY + moveY[i];
            if (map[addX][addY] == -1)
            {
                map[addX][addY] = map[posX][posY] + 1;
                q.push(make_pair(addX, addY));
            }
        }
        q.pop();
    }

    for (int i = 0; i < x; ++i)
    {
        for (int j = 0; j < y; ++j)
            cout << map[i][j] << ' ';
        cout << '\n';
    }
}