[백준] 16236번 : 아기 상어

문제

 

---

풀이

 

계속해서 상어를 이동시키며 이동할 때마다 bfs를 실행해야 한다.

다행히 입력 범위가 그렇게 크지 않아 bfs를 여러번 해도 시간 초과는 발생하지 않는다.

 

상어가 물고기를 먹는 우선순위 때문에 좀 헤맸다.

처음엔 단순히 '상-좌-우-하'의 순서로 탐색하면 되겠거니 했는데 '예제 입력 4'에서 틀린 답이 나왔다.

 

그래서 최단 경로에 위치한 모든 물고기들을 찾은 뒤, 그 물고기들 중에서 가장 우선순위가 높은 물고기를 찾는 방법으로 코드를 다시 작성했다.

---

소스코드

 

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

using namespace std;

vector<vector<int>> board;
int shark_size = 2; //상어의 크기
int fish_cnt, result; //먹은 물고기의 수, 이동하는데 걸린 총 시간
pair<int, int> dir[4] = {{-1, 0},  //상
                         {1,  0},  //하
                         {0,  -1}, //좌
                         {0,  1}}; //우

bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) { //정렬
    if (p1.first == p2.first)
        return p1.second < p2.second;
    return p1.first < p2.first;
}

pair<int, int> bfs(pair<int, int> shark) {
    int size = board.size(), min_dist = 1000;
    queue<pair<int, int>> q; //상어가 갈 수 있는 곳을 담은 큐
    vector<vector<int>> dist; //상어의 방문 여부 및 이동 거리
    dist.assign(size, vector<int>(size, -1));
    vector<pair<int, int>> candi; //상어가 최종적으로 이동할 곳의 후보

    dist[shark.first][shark.second] = 0;
    q.push(shark);
    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();

        if (dist[row][col] < min_dist) { //dist[row][col]이 min_dist 이상이라면, 물고기가 있어도 최단거리가 아님
            for (int i = 0; i < 4; i++) {
                int nr = row + dir[i].first;
                int nc = col + dir[i].second;
                if ((nr >= 0) && (nr < size) && (nc >= 0) && (nc < size) && (dist[nr][nc] == -1) && //범위 내에 있는 미방문 좌표
                    (board[nr][nc] <= shark_size)) { //상어가 갈 수 있다면
                    dist[nr][nc] = dist[row][col] + 1; //거리 갱신
                    if ((board[nr][nc] > 0) && (board[nr][nc] < shark_size)) { //상어가 먹을 수 있는 물고기라면
                        candi.push_back(make_pair(nr, nc)); //최종 이동 후보에 넣음
                        min_dist = dist[nr][nc]; //최단 거리 갱신
                    }
                    if (dist[nr][nc] < min_dist) //먹을 수 있는 물고기를 찾았다면 더 나갈 필요 없음
                        q.push(make_pair(nr, nc));
                }
            }
        }
    }
    if (candi.empty()) //후보 배열이 비어있다면 상어가 이동할 수 없는 것
        return make_pair(-1, -1);

    sort(candi.begin(), candi.end(), cmp); //정렬
    fish_cnt++; //먹은 물고기의 수 증가
    if (fish_cnt == shark_size) { //먹은 물고기의 수가 상어의 크기와 같다면
        fish_cnt = 0;
        shark_size++;
    }
    board[candi[0].first][candi[0].second] = 9; //상어 이동
    board[shark.first][shark.second] = 0; //상어의 원래 위치 0으로 변경
    result += min_dist; //활동 시간 증가
    return make_pair(candi[0].first, candi[0].second); //상어의 새로운 위치 반환
}

int main() {
    int N;
    pair<int, int> shark_pos;

    cin >> N;
    board.assign(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if (board[i][j] == 9) //상어의 초기 위치
                shark_pos = make_pair(i, j);
        }
    }
    while ((shark_pos.first != -1) && (shark_pos.second != -1)) //상어가 더 이동할 수 없을 때까지 이동
        shark_pos = bfs(shark_pos);
    cout << result;
}

전체 소스코드다.

 

vector<vector<int>> board;
int shark_size = 2; //상어의 크기
int fish_cnt, result; //먹은 물고기의 수, 이동하는데 걸린 총 시간
pair<int, int> dir[4] = {{-1, 0},  //상
                         {1,  0},  //하
                         {0,  -1}, //좌
                         {0,  1}}; //우

상어의 크기, 현재 먹은 물고기의 수, 활동 시간은 전역변수로 관리한다.

 

    cin >> N;
    board.assign(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if (board[i][j] == 9) //상어의 초기 위치
                shark_pos = make_pair(i, j);
        }
    }

board에 입력을 받으면서 상어의 초기 위치도 저장한다.

 

    while ((shark_pos.first != -1) && (shark_pos.second != -1)) //상어가 더 이동할 수 없을 때까지 이동
        shark_pos = bfs(shark_pos);

그리고 상어의 위치를 계속 갱신할건데, bfs는 상어가 더이상 이동할 수 없을 때 (-1, -1)을 반환하도록 했다.

그러니 while문의 종료 조건도 (-1, -1)로 하면 된다.

 

pair<int, int> bfs(pair<int, int> shark) {
    int size = board.size(), min_dist = 1000;
    queue<pair<int, int>> q; //상어가 갈 수 있는 곳을 담은 큐
    vector<vector<int>> dist; //상어의 방문 여부 및 이동 거리
    dist.assign(size, vector<int>(size, -1));
    vector<pair<int, int>> candi; //상어가 최종적으로 이동할 곳의 후보

    dist[shark.first][shark.second] = 0;
    q.push(shark);
    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();

        if (dist[row][col] < min_dist) { //dist[row][col]이 min_dist 이상이라면, 물고기가 있어도 최단거리가 아님
            for (int i = 0; i < 4; i++) {
                int nr = row + dir[i].first;
                int nc = col + dir[i].second;
                if ((nr >= 0) && (nr < size) && (nc >= 0) && (nc < size) && (dist[nr][nc] == -1) && //범위 내에 있는 미방문 좌표
                    (board[nr][nc] <= shark_size)) { //상어가 갈 수 있다면
                    dist[nr][nc] = dist[row][col] + 1; //거리 갱신
                    if ((board[nr][nc] > 0) && (board[nr][nc] < shark_size)) { //상어가 먹을 수 있는 물고기라면
                        candi.push_back(make_pair(nr, nc)); //최종 이동 후보에 넣음
                        min_dist = dist[nr][nc]; //최단 거리 갱신
                    }
                    if (dist[nr][nc] < min_dist) //먹을 수 있는 물고기를 찾았다면 더 나갈 필요 없음
                        q.push(make_pair(nr, nc));
                }
            }
        }
    }
    if (candi.empty()) //후보 배열이 비어있다면 상어가 이동할 수 없는 것
        return make_pair(-1, -1);

    sort(candi.begin(), candi.end(), cmp); //정렬
    fish_cnt++; //먹은 물고기의 수 증가
    if (fish_cnt == shark_size) { //먹은 물고기의 수가 상어의 크기와 같다면
        fish_cnt = 0;
        shark_size++;
    }
    board[candi[0].first][candi[0].second] = 9; //상어 이동
    board[shark.first][shark.second] = 0; //상어의 원래 위치 0으로 변경
    result += min_dist; //활동 시간 증가
    return make_pair(candi[0].first, candi[0].second); //상어의 새로운 위치 반환
}

bfs 함수는 먹을 수 있는 물고기의 좌표를 저장하는 부분과 물고기를 실제로 먹는 부분으로 나뉜다.

 

    int size = board.size(), min_dist = 1000;
    queue<pair<int, int>> q; //상어가 갈 수 있는 곳을 담은 큐
    vector<vector<int>> dist; //상어의 방문 여부 및 이동 거리
    dist.assign(size, vector<int>(size, -1));
    vector<pair<int, int>> candi; //상어가 최종적으로 이동할 곳의 후보

    dist[shark.first][shark.second] = 0;
    q.push(shark);

먼저 bfs에 기본적으로 필요한 큐와 거리를 저장하는 벡터를 선언했다.

그리고 최단거리에 있는 물고기들의 좌표를 저장할 candi 벡터와 그 최단거리를 저장할 min_dist 변수도 선언했다.

 

상어의 처음 위치의 dist를 0으로 초기화 하고 그 위치를 큐에 넣으며 시작한다.

 

    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();

        if (dist[row][col] < min_dist) { //dist[row][col]이 min_dist 이상이라면, 물고기가 있어도 최단거리가 아님
            for (int i = 0; i < 4; i++) {
                int nr = row + dir[i].first;
                int nc = col + dir[i].second;
                if ((nr >= 0) && (nr < size) && (nc >= 0) && (nc < size) && (dist[nr][nc] == -1) && //범위 내에 있는 미방문 좌표
                    (board[nr][nc] <= shark_size)) { //상어가 갈 수 있다면
                    dist[nr][nc] = dist[row][col] + 1; //거리 갱신
                    if ((board[nr][nc] > 0) && (board[nr][nc] < shark_size)) { //상어가 먹을 수 있는 물고기라면
                        candi.push_back(make_pair(nr, nc)); //최종 이동 후보에 넣음
                        min_dist = dist[nr][nc]; //최단 거리 갱신
                    }
                    if (dist[nr][nc] < min_dist) //먹을 수 있는 물고기를 찾았다면 더 나갈 필요 없음
                        q.push(make_pair(nr, nc));
                }
            }
        }
    }

특정 좌표의 상하좌우는 그 좌표의 dist값이 min_dist보다 작을 때만 탐색한다.

왜냐하면 특정 좌표에서 상하좌우로 이동하면 무조건 1이 더해질텐데 dist값이 이미 min_dist보다 같거나 컸다면 새롭게 이동한 좌표는 절대 최단 거리에 존재하는 물고기가 될 수 없기 때문이다.

 

                if ((nr >= 0) && (nr < size) && (nc >= 0) && (nc < size) && (dist[nr][nc] == -1) && //범위 내에 있는 미방문 좌표
                    (board[nr][nc] <= shark_size)) { //상어가 갈 수 있다면
                    dist[nr][nc] = dist[row][col] + 1; //거리 갱신
                    if ((board[nr][nc] > 0) && (board[nr][nc] < shark_size)) { //상어가 먹을 수 있는 물고기라면
                        candi.push_back(make_pair(nr, nc)); //최종 이동 후보에 넣음
                        min_dist = dist[nr][nc]; //최단 거리 갱신
                    }
                    if (dist[nr][nc] < min_dist) //먹을 수 있는 물고기를 찾았다면 더 나갈 필요 없음
                        q.push(make_pair(nr, nc));
                }

갈 수 있는 좌표를 계속 탐색하며 큐에 넣어준다.

그러다가 만약 해당 좌표에 먹을 수 있는 물고기가 있다면 min_dist를 갱신하고 그 좌표를 candi 벡터에 넣어준다.

bfs 탐색이기 때문에 처음으로 찾은 물고기의 dist가 min_dist가 될 수 있다.

 

    if (candi.empty()) //후보 배열이 비어있다면 상어가 이동할 수 없는 것
        return make_pair(-1, -1);

    sort(candi.begin(), candi.end(), cmp); //정렬
    fish_cnt++; //먹은 물고기의 수 증가
    if (fish_cnt == shark_size) { //먹은 물고기의 수가 상어의 크기와 같다면
        fish_cnt = 0;
        shark_size++;
    }
    board[candi[0].first][candi[0].second] = 9; //상어 이동
    board[shark.first][shark.second] = 0; //상어의 원래 위치 0으로 변경
    result += min_dist; //활동 시간 증가
    return make_pair(candi[0].first, candi[0].second); //상어의 새로운 위치 반환

while문이 종료되면 candi 벡터에 값이 있는지 확인한다.

만약 값이 없다면 먹을 수 있는 물고기가 없다는 뜻이고 상어가 더이상 이동할 수 없다는 뜻이니 (-1, -1)을 리턴한다.

 

그렇지 않다면 candi 벡터를 정렬한다.

bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) { //정렬
    if (p1.first == p2.first)
        return p1.second < p2.second;
    return p1.first < p2.first;
}

이렇게하면 조건에 맞는 물고기의 좌표가 맨 앞으로 온다.

 

    fish_cnt++; //먹은 물고기의 수 증가
    if (fish_cnt == shark_size) { //먹은 물고기의 수가 상어의 크기와 같다면
        fish_cnt = 0;
        shark_size++;
    }
    board[candi[0].first][candi[0].second] = 9; //상어 이동
    board[shark.first][shark.second] = 0; //상어의 원래 위치 0으로 변경
    result += min_dist; //활동 시간 증가
    return make_pair(candi[0].first, candi[0].second); //상어의 새로운 위치 반환

물고기를 먹어야 하니 fish_cnt를 하나 늘려준다.

근데 만약 이 fish_cnt가 shark_size와 같다면 상어의 크기가 커질 수 있으니 그럴 경우 shark_size를 늘려주고 fist_cnt는 다시 0으로 초기화 한다.

 

그리고 상어의 새로운 위치를 board 벡터에 반영하고 min_dist를 result에 더해준다.

마지막으로 상어의 새로운 위치를 리턴하면 된다.