2020 상반기 삼성SW역량테스트 :: 아기 상어

문제

문제링크

문제접근

기본적인 시뮬레이션 문제로 어렵지 않게 풀 수 있는 문제였습니다.
문제에서 주어진 조건을 차근차근 살펴봅시다.

아기 상어의 규칙

1. 아기 상어는 상, 하, 좌, 우 인접한 칸으로 이동합니다.
2. 아기 상어는 자신보다 작은 물고기만 먹습니다.
   아기 상어는 자신보다 큰 물고기가 있는 칸은 지나갈 수 없습니다.
3. 먹을 수 있는 물고기가 있다면
   1. 한 마리 뿐이라면 해당 물고기를 먹으러 이동합니다.
   2. 여러 마리라면 좌표상으로 위쪽, 왼쪽에 있는 물고기를 먹습니다.
4. 더 이상 먹을 수 있는 물고기가 없을 때까지 반복합니다.

풀이 과정

1. 풀이 방법을 선택해야합니다. 주어진 공간의 크기 N이 2 ≤ N ≤ 20이므로 범위가 작고, 제한시간은 2초입니다.
   • Bruteforce - 범위가 작고 시간이 널널하기 때문입니다.
   • 최단거리 알고리즘 (Dijkstra) - 구현하기 쉽고 가장 직관적입니다.
2. 상어의 현재 위치에서 먹을 수 있는 먹이 후보들을 탐색합니다.
3. 각 먹이 후보들을 먹기까지의 cost를 다익스트라 알고리즘으로 빠르게 구합니다.
4. cost가 가장 낮은 후보로 이동해서 먹이를 먹습니다.
   • 먹은 물고기 개수가 상어 크기와 같다면 상어 크기를 증가시킵니다.
   • 먹은 물고기 개수는 0으로 초기화합니다.
5. 더 이상 먹을 수 있는 물고기가 없을 때까지 2~4 과정을 반복합니다.

코드

// https://www.acmicpc.net/problem/16236
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
using t = tuple<int, int, int>;

static int N, ocean[20][20], dist[20][20], eatCount, sharkSize = 2;
static pair<int, int> curSharkPos, preyPos;
static constexpr int moving[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

bool dijkstra() {
    // dist 배열 초기화, 시작 위치는 거리가 0이다.
    fill(&dist[0][0], &dist[N - 1][N], 1e9);
    dist[curSharkPos.first][curSharkPos.second] = 0;
    // Min heap 초기화, 시작 위치 정보(y, x, cost)를 넣는다.
    priority_queue<t, vector<t>, greater<t>> pq;
    pq.push({curSharkPos.first, curSharkPos.second, 0});

    vector<t> prey;
    while(!pq.empty()) {
        int y, x, cost; tie(y, x, cost) = pq.top();
        pq.pop();
        if (dist[y][x] < cost) continue;

        for (int i = 0; i < 4; ++i) {
            int ny = y + moving[i][0], nx = x + moving[i][1];            
            if (ny < 0 || ny >= N || nx < 0 || nx >= N || ocean[ny][nx] > sharkSize) continue;

            int newCost = cost + 1;
            if (dist[ny][nx] > newCost) {
                dist[ny][nx] = newCost;
                pq.push({ny, nx, newCost});
		// 먹잇감 후보를 찾았다면 배열에 넣는다.
                if (ocean[ny][nx] != 0 && ocean[ny][nx] < sharkSize) prey.push_back({newCost, ny, nx});
            }
        }
    }
    if (!prey.empty()) { 
        sort(begin(prey), end(prey));	// 먹잇감을 cost - y - x 순으로 오름차순 정렬한다.
        preyPos = {get<1>(prey.front()), get<2>(prey.front())};	// 다음 먹잇감을 고르고 반환한다.
        return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < N; ++x) {
            cin >> ocean[y][x];
            if (ocean[y][x] == 9) {		// 상어의 위치 파악 시 기록한다.
                curSharkPos = {y, x};
                ocean[y][x] = 0;		// 그리고 상어가 있는 칸은 빈칸으로 바꾼다.
            }
        }
    int answer = 0;
    while (dijkstra()) {// 다익스트라 결과, 먹잇감을 찾았다면 while 반복문 진행.
	// 먹잇감까지 최단경로를 answer에 더해주고 카운트 결과에 따라 상어 크기 증가.
        answer += dist[preyPos.first][preyPos.second];
        if (++eatCount == sharkSize) {
            sharkSize++;
            eatCount = 0;
        }
        ocean[preyPos.first][preyPos.second] = 0;	// 먹힌 먹잇감은 사라지므로 0으로 표시해준다.
        curSharkPos = preyPos;	// 현재 상어의 위치를 갱신해준다.
    }
    cout << answer << '\n';
}

결과