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

이제 슬슬 삼성 기출에 익숙해진 듯 하다.

문제 및 입출력

문제에서 추출할 수 있는 정보는 다음과 같다.

• 아기 상어의 초기 크기는 2이고 1초마다 상하좌우로 이동한다.
• 자신의 크기보다 큰 물고기는 지나갈 수 없다.
• 자신의 크기보다 작은 물고기는 먹을 수 있다.
• 먹을 수 있는 물고기가 여러 개면 조건에 따라 정렬해야 한다.
• 먹을 수 있는 물고기가 없다면 정답을 출력한다.
• 물고기를 먹는 데 걸리는 시간은 없다.
• 물고기를 잡아먹었을 경우 그 칸은 빈 칸이 된다.
• 자신의 크기만큼의 물고기를 먹으면 크기가 1 증가한다.

해결 과정

먼저 상어와 물고기가 있는 공간의 상황을 표현할 수 있는 자료형 및 변수를 세팅하자.

struct fish { // 물고기 구조체: (아기 상어로부터의) 거리, 좌표
    int dis;
    int x;
    int y;
    fish(int d, int a, int b){
        dis = d;
        x = a;
        y = b;
    }
};
int n;
bool flag = true; // 종료 조건
pair<int, int> nowpos; // 현재 위치
int nowsize = 2; // 현재 크기
int noweat = 0; // 현재 레벨업 전까지 먹은 물고기 수
int answer = 0; // 정답
vector<fish> fishes; // 물고기들
int map[21][21];
int visited[21][21];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

물고기의 특성을 표현할 구조체와 BFS를 위한 여러 배열, 상어의 크기, 위치, 물고기 수 등을 표현해 두었다.

나는 while문 내부 BFS를 통해 상어의 현재 위치로부터 먹을 수 있는 물고기들을 fishes에 담은 후, 조건에 따라 정렬한 뒤 맨 앞의 물고기의 위치로 상어가 이동하도록 할 것이다.
fishes가 비어있다면 반복문을 종료하고 결과를 출력해야 한다.

bool cmp(fish f1, fish f2){ // 먹을 수 있는 물고기 정렬
    if(f1.dis == f2.dis) {
        if(f1.x == f2.x) {  
            return f1.y < f2.y; // 왼쪽 오름차순
        }
        return f1.x < f2.x; // 위쪽 오름차순
    }
    return f1.dis < f2.dis; // 상어로부터의 거리 오름차순
}

초반에 언급한 다양한 조건을 적절히 결합하여 BFS를 구현하면 된다.

void BFS(int sx, int sy){
    fishes.clear();
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int> > q;
    visited[sx][sy] = 1;
    q.push(make_pair(sx, sy));
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

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

            if(nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) continue;
            if(map[nx][ny] > nowsize) continue; // 크기가 큰 물고기 칸을 지나갈 수 없음

            visited[nx][ny] = visited[x][y] + 1;
            q.push(make_pair(nx, ny));
            if(map[nx][ny] > 0 && map[nx][ny] < nowsize){ // 먹을 수 있는 물고기
                fishes.push_back(fish(visited[nx][ny]-1, nx, ny));
            }
        }
    }
    if(fishes.empty()) { // 비어있으면 종료
        flag = false;
        return;
    }
    if(fishes.size() >= 2) // 2개 이상이면 정렬
        sort(fishes.begin(), fishes.end(), cmp);
    answer += fishes[0].dis;
    nowpos = make_pair(fishes[0].x, fishes[0].y); // 현재 위치 갱신
    map[fishes[0].x][fishes[0].y] = 0; // 빈 칸이 됨
}

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

struct fish { // 생선 구조체
    int dis;
    int x;
    int y;
    fish(int d, int a, int b){
        dis = d;
        x = a;
        y = b;
    }
};
int n;
bool flag = true;
pair<int, int> nowpos; // 상어 현재 위치
int nowsize = 2; // 상어 크기
int noweat = 0; // 상어가 레벨업 전까지 먹은 물고기
int map[21][21];
int visited[21][21];
int answer = 0;
vector<fish> fishes;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

bool cmp(fish f1, fish f2){ // 먹을 수 있는 물고기 정렬
    if(f1.dis == f2.dis) {
        if(f1.x == f2.x) {  
            return f1.y < f2.y;
        }
        return f1.x < f2.x;
    }
    return f1.dis < f2.dis;
}

void BFS(int sx, int sy){
    fishes.clear();
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int> > q;
    visited[sx][sy] = 1;
    q.push(make_pair(sx, sy));
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

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

            if(nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) continue;
            if(map[nx][ny] > nowsize) continue; // 크기가 큰 물고기 칸을 지나갈 수 없음

            visited[nx][ny] = visited[x][y] + 1;
            q.push(make_pair(nx, ny));
            if(map[nx][ny] > 0 && map[nx][ny] < nowsize){ // 먹을 수 있는 물고기
                fishes.push_back(fish(visited[nx][ny]-1, nx, ny));
            }
        }
    }
    if(fishes.empty()) { // 비어있으면 종료
        flag = false;
        return;
    }
    if(fishes.size() >= 2) // 2개 이상이면 정렬
        sort(fishes.begin(), fishes.end(), cmp);
    answer += fishes[0].dis;
    nowpos = make_pair(fishes[0].x, fishes[0].y); // 현재 위치 갱신
    map[fishes[0].x][fishes[0].y] = 0; // 빈 칸이 됨
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
            if(map[i][j] == 9){
                nowpos = make_pair(i, j);
                map[i][j] = 0;
            }
        }
    }

    while(1){
        BFS(nowpos.first, nowpos.second);
        if(!flag) break;

        if(++noweat == nowsize){ // 현재 크기와 같은수만큼 먹었으면 크기 증가
            noweat = 0;
            nowsize++;
        }
    }
    cout << answer;
    return 0;
}

교훈

• 정보량이 과한 것 같으면 일단 비문학 읽듯이 정리한 뒤에 코딩을 시작하면 좋다.