문제

in Blog_old on Boj, 삼성sw역량테스트기출, C++

링크

$N \times N$ 공간에 물고기 여러 마리와 아기 상어가 있고, 크기와 관련된 규칙이 존재한다. 이 규칙에 따라 움직일 때 움직이는 거리(택시 거리)를 구하는 문제이다.

접근

문제를 꼼꼼히 읽고 그대로 구현하면 어렵지 않게 풀 수 있다. N에 대한 제한이 작아서($N\leq20$) 시간이나 메모리 제한이 빡빡하지도 않다.

BFS를 이용하여 현재 위치로부터 각 칸의 거리를 구하고, 잡아먹을 수 있는 물고기 중 가장 위쪽이면서 가장 왼쪽에 있는 물고기를 찾아 상어를 옮겨주자. 더 이상 잡아먹을 수 있는 물고기가 없을 때까지 반복하면 된다.

주의할 점

가장 가까운 물고기가 여러 마리 있다면 가장 위쪽의 물고기를, 이것도 여러 마리라면 그 중 가장 왼쪽 물고기를 골라야 한다. 이를 단순히 BFS할 때 위쪽, 왼쪽, 아래/오른쪽 순서대로 처리하도록 해서는 안된다. 곰곰이 생각해보면 현재 상어 크기보다 큰 물고기를 통과하지 못하는 규칙이 있어서, 아래로 출발했다가 위로 가는 경로가 반례가 될 수 있음을 알 수 있다.

BFS할 때 거리의 최대값을 초기화 한다면, 400 이상으로 넉넉히 잡아야 한다. (아무 생각 없이 100으로 잡았다가 틀렸습니다를 한 번 당했다.)

Code

링크

#include <iostream>
#include <utility>
#include <tuple>
#include <deque>

using namespace std;

int n;
int board[20][20];
int shark_r, shark_c, shark_size, shark_acc;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int MAX_DIST = 1000;

tuple<int, int, int> bfs()
{
    int visited[20][20] = {0};
    int distance[20][20] = {0};
    int min_dist = MAX_DIST;
    visited[shark_r][shark_c] = 1;
    distance[shark_r][shark_c] = 0;
    deque<tuple<int, int, int>> queue;
    queue.push_back(make_tuple(shark_r, shark_c, 0));
    while (!queue.empty())
    {
        int x, y, dist;
        tie(x, y, dist) = queue.front();
        queue.pop_front();
        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 < n && !visited[nx][ny] && board[nx][ny] <= shark_size)
            {
                if (board[nx][ny] != 0 && board[nx][ny] < shark_size)
                {
                    min_dist = min(min_dist, dist + 1);
                }
                visited[nx][ny] = 1;
                distance[nx][ny] = dist + 1;
                queue.push_back(make_tuple(nx, ny, dist + 1));
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (distance[i][j] == min_dist && board[i][j] != 0 && board[i][j] < shark_size)
                return make_tuple(i, j, min_dist);
        }
    }

    return make_tuple(-1, -1, -1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 9)
            {
                board[i][j] = 0;
                shark_r = i;
                shark_c = j;
            }
        }
    }
    shark_size = 2;
    shark_acc = 0;
    int ans = 0;
    while (true)
    {
        int x, y, d;
        tie(x, y, d) = bfs();
        if (d == -1)
            break;
        shark_r = x;
        shark_c = y;
        ans += d;
        shark_acc += 1;
        board[x][y] = 0;
        if (shark_acc == shark_size)
        {
            shark_acc = 0;
            shark_size++;
        }
    }
    cout << ans;
    return 0;
}

여담

항상 Python을 써와서 C++로 구현하느라 시간이 오래 걸렸다. 솔직히 위에 코드는 별로 깔끔하지는 않아서 부끄럽지만… 풀었던 흔적을 남기는 거니까😁