[BOJ 16236] 아기 상어

1. 문제 설명

• 조건: 더 이상 먹을 수 있는 물고기가 공간에 없다면 엄마 상어에게 도움을 요청한다
• 요구사항: 몇 초동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는가?

이 두 문장을 합하면 더 이상 먹을 수 있는 물고기가 없을 때까지 걸리는 시간을 구해야 한다는 것을 알 수 있다.

 

물고기를 먹는 조건을 다시 정리하면 아래와 같다.

1. 물고기의 크기가 아기 상어의 크기보다 작아야 한다.
2. 거리가 가까운 순 > X 좌표가 작은 순 > Y 좌표가 작은 순
   • X = 행, Y = 열

 

2. 구현 아이디어 1 - 틀렸습니다

이번 문제는 BFS + 빡구현 유형이다.

주어진 조건이 다소 많은데, 해당 조건들을 충족하도록 차근차근 꼼꼼하게 구현하면 풀 수 있다.

 

아기 상어와 관련된 변수는 걸린 시간, 상어의 크기, 먹은 물고기의 개수가 필요하고, 물고기와 관련된 변수는 물고기의 크기와 좌표가 필요하다.

둘 다 변수가 3개 이상이므로 변수를 편하게 관리하기 위해 구조체로 변수를 관리하였다.

(물고기는 이중 pair로도 가능하지만 이중 pair을 사용하면 헷갈리기 쉽다)

 

문제를 풀기 위해 내가 생각한 로직은 아래와 같다.

 

1. 입력을 받을 때, 물고기의 위치를 fishes라는 배열에 저장한다
   • 처음에는 아기 상어-물고기를 INF로 초기화하고 BFS를 돌며 최단 거리를 갱신한다
2. 무한 루프를 돌며, 더 이상 먹을 수 있는 물고기가 없을 경우 break로 반복문을 탈출한다.
   • fishes를 순회하며 BFS로 각 물고기-아기 상어 사이의 거리를 구한다
   • 주어진 조건(거리 순, 좌표 작은 순)에 따라 fishes 배열을 정렬한다 → 0번째 원소가 아기 상어가 이동할 다음 칸이 된다
   • 걸리는 시간에 물고기-아기 상어 거리를 더하고, 상어의 좌표를 이동시키고, 먹은 물고기의 갯수와 상어의 크기를 갱신하고, 공간에서 물고기를 지운다.

 

BFS에서 기본 확인 조건(인덱스가 공간을 벗어나는 경우, 이미 방문한 경우)에 추가적으로 다음 칸에 물고기가 있을 경우 아기 상어보다 큰 경우를 확인해주어야 한다.

 

그리고 정렬 조건을 커스텀할 수 있도록 compare 함수를 따로 만들어주고, sort 함수의 인자로 사용해주었다.

 

코드가 길기 때문에 각 부분마다 나누어 첨부하겠다. (최종 정답 코드는 하단 참고)

 

아기 상어와 물고기 구조체

struct Shark {
    pair<int, int> point; // 좌표
    int cnt = 0; // 먹은 물고기 수
    int size = 2; // 아기 상어의 크기
};

struct Fish {
    int dist = INF; // 아기 상어와의 거리
    int size = 0; // 크기
    pair<int, int> point;

    Fish(int d, int s, int x, int y) {
        this->dist = d;
        this->size = s;
        this->point = {x, y};
    }
};

 

BFS

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void bfs(vector<vector<int>> &board, vector<Fish> &fishes, Shark &shark) {
    for (int i = 0; i < fishes.size(); ++i) {
        // 아기 상어보다 큰 물고기는 먹을 수 없음 > dist = INF
        if (fishes[i].size >= shark.size) {
            fishes[i].dist = INF;
            continue;
        }

        queue<pair<int, pair<int, int>>> q; // { {거리, 좌표}, {거리, 좌표} ....}
        vector<vector<int>> visited = vector<vector<int>>(board.size(), vector<int>(board.size(), false));

        // 초기화
        auto goal = fishes[i].point;
        q.push({0, shark.point});
        visited[shark.point.X][shark.point.Y] = true;

        // BFS
        while (!q.empty()) {
            int dist = q.front().first;
            int cx = q.front().second.X;
            int cy = q.front().second.Y;
            q.pop();

            if (goal == make_pair(cx, cy)) {
                fishes[i].dist = dist;
                break;
            }

            for (int j = 0; j < 4; ++j) {
                int nx = cx + dx[j];
                int ny = cy + dy[j];

                // Out of Range
                if (nx < 0 || ny < 0 || nx >= board.size() || ny >= board.size()) continue;
                // 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다
                if (board[nx][ny] > shark.size) continue;
                // 이미 방문한 경우
                if (visited[nx][ny]) continue;

                q.push({dist+1, make_pair(nx, ny)});
                visited[nx][ny] = true;
            }
        }
    }
}
}

 

정렬 조건 커스텀

// 가장 거리가 가까운 물고기 > 가장 위(x좌표가 작을수록) > 가장 왼쪽 (y좌표가 작을수록)
bool compare(Fish a, Fish b) {
    if (a.dist < b.dist) return true;
    else if (a.dist == b.dist && a.point.X < b.point.X) return true;
    else if (a.dist == b.dist && a.point.X == b.point.X) return a.point.Y < b.point.Y;

    return false;
}

 

main 함수

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

    int n; // 공간의 크기 (최대 20)
    cin >> n;

    vector<vector<int>> board = vector<vector<int>>(n, vector<int>(n, 0));
    vector<Fish> fishes;
    Shark shark;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> board[i][j];

            // 아기 상어의 위치
            if (board[i][j] == BABY_SHARK) {
                shark.point = {i, j};
                shark.cnt = 0;
                board[i][j] = 0;
            }

            // 물고기의 위치
            if (board[i][j] >= 1 && board[i][j] <= 6) {
                Fish fish = Fish(INF, board[i][j], i, j);
                fishes.push_back(fish);
            }
        }
    }

    // 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지
    // = 더 이상 먹을 수 있는 물고기가 공간에 없다면 프로그램 종료
    // 가장 거리가 가까운 물고기 > 가장 위(x좌표가 작을수록) > 가장 왼쪽 (y좌표가 작을수록)
    // 물고기는 최대 399개
    int ret = 0; // 걸리는 시간

    // 시작점과 물고기들 사이의 거리를 구한다
    bfs(board, fishes, shark);

    // 1. fishes를 순회하며 BFS로 dist 갱신 (fish.size >= shark.size일 경우 dist=-1)
    // 3. 만약 fish.size >= shark.size라면 while문 탈출
    // 4. 그렇지 않다면 fishes[0]을 먹고, 그 자리로 이동
    while(true) {
        // 물고기가 공간에 없을 경우
        if (fishes.empty()) break;

        bfs(board, fishes, shark);
        sort(fishes.begin(), fishes.end(), compare);

        // 물고기는 있는데 모두 아기 상어보다 클 경우
        if (!canEat(fishes, shark)) break;

        Fish target = fishes[0];

        ret += target.dist; // 걸리는 시간 더함
        shark.point = target.point; // 상어의 좌표 이동
        // 자신의 크기와 같은 수의 물고기를 먹으면 크기 1 증가
        shark.cnt++;
        if (shark.cnt == shark.size) {
            shark.size++;
            shark.cnt = 0;
        }
        board[target.point.X][target.point.Y] = 0; // 물고기 사라짐
        fishes.erase(fishes.begin()); // 물고기 사라짐
    }

    cout << ret << "\n";
}

 

3. 구현 아이디어 2 - 맞았습니다!!

글 읽기 - 16236 아기 상어 반례 16개 모음

 

질문 게시판의 반례 모음을 참고하여 잘못된 부분을 찾았다.

반례 16개 중 1, 9, 16, 17번을 통과하지 못하였다.

4가지 반례 모두 상어가 이동할 칸이 없을 때를 고려하지 못해서 틀렸던 것이다.

가장 쉬운 17번 반례를 봐보자.

2
9 3
3 1

 

아기 상어(9)가 이동할 수 있는 칸에 있는 물고기의 크기(=3)가 모두 상어의 크기(=2)보다 크므로 상어는 더 이상 이동할 칸이 없다.

더 이상 이동할 칸이 없는 경우, fishes 배열의 모든 거리값이 INF이므로 INF가 출력되던 것이였다.

 

아래와 같이 while문에서 가장 우선순위가 높은 물고기가 있는 칸에 도달할 수 없는 경우(fish[0].dist == INF) 반복문을 탈출하도록 코드를 수정하여 문제를 해결할 수 있었다! (변경지점이라고 주석 단 부분 참고)

while(true) {
    // 물고기가 공간에 없을 경우
    if (fishes.empty()) break;
    // 물고기는 있는데 모두 아기 상어보다 클 경우
    if (!canEat(fishes, shark)) break;

    bfs(board, fishes, shark);
    sort(fishes.begin(), fishes.end(), compare);

    Fish target = fishes[0];
    // 변경 지점 !!! 이동할 수 있는 칸이 없을 경우
    if (target.dist == INF) break;

    ret += target.dist; // 걸리는 시간 더함
    shark.point = target.point; // 상어의 좌표 이동
    // 자신의 크기와 같은 수의 물고기를 먹으면 크기 1 증가
    shark.cnt++;
    if (shark.cnt == shark.size) {
        shark.size++;
        shark.cnt = 0;
    }
    board[target.point.X][target.point.Y] = 0; // 물고기 사라짐
    fishes.erase(fishes.begin()); // 물고기 사라짐
}

 

4. 전체 코드

#include <bits/stdc++.h>

using namespace std;

#define BABY_SHARK 9
#define X first
#define Y second
#define INF 987654321

struct Shark {
    pair<int, int> point; // 좌표
    int cnt = 0; // 먹은 물고기 수
    int size = 2; // 아기 상어의 크기
};

struct Fish {
    int dist = INF; // 아기 상어와의 거리
    int size = 0; // 크기
    pair<int, int> point;

    Fish(int d, int s, int x, int y) {
        this->dist = d;
        this->size = s;
        this->point = {x, y};
    }
};

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void bfs(vector<vector<int>> &board, vector<Fish> &fishes, Shark &shark) {
    for (int i = 0; i < fishes.size(); ++i) {
        // 아기 상어보다 큰 물고기는 먹을 수 없음 > dist = INF
        if (fishes[i].size >= shark.size) {
            fishes[i].dist = INF;
            continue;
        }

        queue<pair<int, pair<int, int>>> q; // { {거리, 좌표}, {거리, 좌표} ....}
        vector<vector<int>> visited = vector<vector<int>>(board.size(), vector<int>(board.size(), false));

        // 초기화
        auto goal = fishes[i].point;
        q.push({0, shark.point});
        visited[shark.point.X][shark.point.Y] = true;

        // BFS
        while (!q.empty()) {
            int dist = q.front().first;
            int cx = q.front().second.X;
            int cy = q.front().second.Y;
            q.pop();

            if (goal == make_pair(cx, cy)) {
                fishes[i].dist = dist;
                break;
            }

            for (int j = 0; j < 4; ++j) {
                int nx = cx + dx[j];
                int ny = cy + dy[j];

                // Out of Bounds
                if (nx < 0 || ny < 0 || nx >= board.size() || ny >= board.size()) continue;
                // 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다
                if (board[nx][ny] > shark.size) continue;
                // 이미 방문한 경우
                if (visited[nx][ny]) continue;

                q.push({dist+1, make_pair(nx, ny)});
                visited[nx][ny] = true;
            }
        }
    }
}

bool canEat(vector<Fish> &fishes, Shark shark) {
    for (auto fish : fishes) {
        if (fish.size < shark.size) return true;
    }

    return false;
}

// 가장 거리가 가까운 물고기 > 가장 위(x좌표가 작을수록) > 가장 왼쪽 (y좌표가 작을수록)
bool compare(Fish a, Fish b) {
    if (a.dist < b.dist) return true;
    else if (a.dist == b.dist && a.point.X < b.point.X) return true;
    else if (a.dist == b.dist && a.point.X == b.point.X) return a.point.Y < b.point.Y;

    return false;
}

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

    int n; // 공간의 크기 (최대 20)
    cin >> n;

    vector<vector<int>> board = vector<vector<int>>(n, vector<int>(n, 0));
    vector<Fish> fishes;
    Shark shark;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> board[i][j];

            // 아기 상어의 위치
            if (board[i][j] == BABY_SHARK) {
                shark.point = {i, j};
                shark.cnt = 0;
                board[i][j] = 0;
            }

            // 물고기의 위치
            if (board[i][j] >= 1 && board[i][j] <= 6) {
                Fish fish = Fish(INF, board[i][j], i, j);
                fishes.push_back(fish);
            }
        }
    }

    // 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지
    // = 더 이상 먹을 수 있는 물고기가 공간에 없다면 프로그램 종료
    // 가장 거리가 가까운 물고기 > 가장 위(x좌표가 작을수록) > 가장 왼쪽 (y좌표가 작을수록)
    // 물고기는 최대 399개
    int ret = 0; // 걸리는 시간

    // 시작점과 물고기들 사이의 거리를 구한다
    bfs(board, fishes, shark);

    // 1. fishes를 순회하며 BFS로 dist 갱신 (fish.size >= shark.size일 경우 dist=-1)
    // 3. 만약 fish.size >= shark.size라면 while문 탈출
    // 4. 그렇지 않다면 fishes[0]을 먹고, 그 자리로 이동
    while(true) {
        // 물고기가 공간에 없을 경우
        if (fishes.empty()) break;
        // 물고기는 있는데 모두 아기 상어보다 클 경우
        if (!canEat(fishes, shark)) break;

        bfs(board, fishes, shark);
        sort(fishes.begin(), fishes.end(), compare);

        Fish target = fishes[0];
        if (target.dist == INF) break;

        ret += target.dist; // 걸리는 시간 더함
        shark.point = target.point; // 상어의 좌표 이동
        // 자신의 크기와 같은 수의 물고기를 먹으면 크기 1 증가
        shark.cnt++;
        if (shark.cnt == shark.size) {
            shark.size++;
            shark.cnt = 0;
        }
        board[target.point.X][target.point.Y] = 0; // 물고기 사라짐
        fishes.erase(fishes.begin()); // 물고기 사라짐
    }

    cout << ret << "\n";
}

---

이번 문제는 삼성 SW 역량 테스트(A형)의 대표적인 기출 문제이다. A형은 2문제를 3시간 안에 풀어야 하므로 1문제 당 1시간 30분 내에 풀어야 한다. 하지만 이번 문제를 푸는데 2시간 넘게 소요됐다 ㅠㅠ

요즘 문제를 풀 때 최대한 효율적인 자료형을 선택하느라 고민 시간이 많이 소요되는데, 문제를 효율적으로 풀기 위해 변수의 범위를 보고 적당히 작을 경우에는 당장 떠오르는 자료형을 사용하여 빠르게 푸는 연습을 해야겠다.

 

아! 그리고 compare 함수를 구현할 때 if-else문도 처음에는 잘못 작성하였는데, else if문에서 우선 순위의 조건이 같을 경우를 추가해주어야 하는 것을 잊지 말자.

• a.dist == b.dist && a.point.X < b.point.X (O)
• a.point.X < b.point.X (X)
  • a.dist > b.dist인데 우선순위가 높아질 수 있다