[백준/c++] 17129 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

 

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

17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

 

✨ 문제 풀이

2가 딱따구리 가족이므로 2의 (y, x)좌표가 시작점이 될 것입니다. 그리고 3, 4, 5는 딱따구리 가족이 각자 먹고 싶은 음식이고 종착점이 됩니다. 딱따구리 가족은 3, 4, 5 중 아무거나 하나만 가장 먼저 먹을 수 있는지만 구하면 됩니다. 1은 장애물이라 갈 수 없으며 0은 지나갈 수 있습니다. 딱따구리 가족은 한 번에 한 칸씩, 상하좌우 4방향으로만 움직일 수 있습니다.

 

n*m 모양의 격자 무늬 행렬을 BFS를 이용해 푸는 문제입니다. 아래 코드를 응용할게요.

https://shunnyjang.tistory.com/17

[c++] n*m 격자 무늬, 행렬 BFS 알고리즘 문제 코드

 

🗓 코드

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

#define MAXINT 3001

int n, m, start_y, start_x;
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};

int map[MAXINT][MAXINT];
int dist[MAXINT][MAXINT];
queue<pair<int, int>> location;

void getInput()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        char *temp = new char[m];
        scanf("%s", temp);
        for (int j = 0; j < m; j++)
        {
            map[i][j] = temp[j] - '0';
            if (map[i][j] == 2)
                start_y = i, start_x = j;
        }
    }
}

int solve()
{
    dist[start_y][start_x] = 0;
    location.push({start_y, start_x});
    while (!location.empty())
    {
        int y = location.front().first;
        int x = location.front().second;
        location.pop();

        // 3, 4, 5 중 하나에 도착하면 거리를 반환하고 종료
        if (map[y][x] > 2)
            return dist[y][x];

        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
            // 장애물(1)이거나 방문한 적 있는 격자는 다음에 방문하지 않음
            if (map[ny][nx] == 1 || dist[ny][nx] > 0)
                continue;
            dist[ny][nx] = dist[y][x] + 1;
            location.push({ny, nx});
        }
    }
    // 3, 4, 5 중 아무것도 만나지 못하고 탐색 완전 종료
    return -1;
}

void getResult()
{
    int result = solve();
    if (result > 0)
        printf("TAK\n%d", result);
    else
        printf("NIE\n");
}

int main(int argc, char const *argv[])
{
    getInput();
    getResult();
    return 0;
}

 

이때 시작점은 2의 좌표, 종착점은 3 또는 4또는 5의 좌표가 될 것이고 몇 개의 0을 지나서 갈 수 있는지 구해야 합니다. 따라서 (y, x)에 도달하는 데 몇 개의 0을 지나서 올 수 있는지 거리를 저장하는 배열 dist[i][j]를 선언하겠습니다. dist에 0 이상의 값이 이미 있으면 방문했다는 표시와 같으니 visited는 dist로 대체합니다.

int dist[MAXINT][MAXINT]

장애물인 1을 만나면 방문할 좌표를 저장하는 큐에 저장하지 않습니다. 당연히 방문한 적 있는 좌표도 다시 방문하지 않기 때문에 dist[i][j] 값이 0보다 크면 큐에 저장하지 않습니다.

if (map[ny][nx] == 1 || dist[ny][nx] > 0)
                continue;

장애물이 아니고 갈 수 있는 위치라면 방문할 좌표로 큐에 저장합니다.

dist[ny][nx] = dist[y][x] + 1;
location.push({ny, nx});

이때 3, 4, 5 중 하나에 먼저 도착하게 되면 그 때 거리를 구하고 종료합니다.

if (map[y][x] > 2)
    return dist[y][x];