📌문제

> 문제 보기

코드

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

#define MAX_SIZE 21

using namespace std;

int space[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];
int dir[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
int n;
int shark = 2;
int x, y, eat = 0; // 아기 상어 위치
int ans = 0;

bool compare(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2) {
    if (p1.second == p2.second) { // 거리 순
        if (p1.first.first == p2.first.first) { // first.first = x
            return p1.first.second < p2.first.second;   // first.second = y
        }
        else {
            return p1.first.first < p2.first.first;
        }
    }
    else {
        return p1.second < p2.second; // second = count 이동 거리
    }
}

void bfs() {
    while (1) {
        queue<pair<pair<int, int>, int>> q;
        memset(visited, false, sizeof(visited)); // 방문 초기화
        
        q.push({{x, y}, 0});    // 위치. 이동 거리
        visited[x][y] = true;

        vector<pair<pair<int, int>, int>> eatable;

        while (!q.empty()) {
            int cx = q.front().first.first;   // current x
            int cy = q.front().first.second;  // current y
            int count = q.front().second;

            q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = cx + dir[i][0];
                int ny = cy + dir[i][1];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (!visited[nx][ny]) {
                        if (space[nx][ny] <= shark) { // 지나갈 수 있음
                            q.push({{nx, ny}, count + 1});
                            visited[nx][ny] = true;
                            if (space[nx][ny] != 0 && space[nx][ny] < shark) {
                                eatable.push_back({{nx, ny}, count + 1});
                            }
                        } // 크면 지나갈 수 없고 먹을 수도 없음
                    }
                }   
            }
        }

        if (eatable.empty()) {	// 먹을 수 있는 물고기가 없는 경우
            cout << ans << '\n';
            break;
        }
        else { 			// 먹을 수 있는 물고기가 있는 경우	
            // 거리순, 위에 있는 순, 왼쪽 순서대로 정렬
            sort(eatable.begin(), eatable.end(), compare);
            
            // 아기 상어 위치 업데이트
            x = eatable[0].first.first;
            y = eatable[0].first.second;
            space[x][y] = 0;	// 먹이 먹음
            eat++;
            ans += eatable[0].second;	// 걸리는 시간

            if (shark == eat) { // 자신의 크기와 같은 수를 먹은 경우
                eat = 0;	
                shark++;
            }
        }
    }
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> space[i][j];
            if (space[i][j] == 9) {
                x = i;
                y = j;
                space[i][j] = 0;	// 아기 상어 위치 기록 후 초기화
            }
        }
    }

    bfs();

    return 0;
}

왜 코드 접기 펴기가 없어..

🍳풀이 방법

상어 이동 조건

1. 먹을 수 있는 물고기가 없으면 엄마 상어에게 도움 요청 (종료)
2. 먹을 수 있는 물고기가 있다면
   2-1. 가장 가까운 물고기를 먹으러 간다
   2-2. 같은 거리에 물고기가 여러마리 있으면, 위 -> 왼쪽 순으로 먹는다

가장 가까운 물고기를 먹으러 간다는 조건이 있어 BFS 를 사용한다고 생각했다.
1. 이동할 수 있는 거리(상,하,좌,우 탐색)를 Q에 모두 집에 넣고, 먹을 수 있는 먹이가 있으면 eatable에 넣는다.
2. Q 탐색이 끝난 뒤, eatable이 비어있으면 먹을 수 있는 물고기가 없으므로 종료한다
3. eatable이 비어있지 않으면, 거리(걸린 시간) > 위 > 왼쪽 순서대로 정렬하여 0번째 인덱스 값으로 상어의 위치를 이동한다.

0번째 값이 가장 가깝거나, 위쪽, 혹은 왼쪽에 있는 경우

❗❗ 실패 원인

처음에 단순하게 BFS 탐색하다가 먹을 수 있는 먹이를 만나면 종료한 뒤에 먹는 방향으로 작성했었다.
이렇게 코드를 짜면 가장 위쪽, 혹은 가장 왼쪽의 물고기를 탐색하지 않아버리므로 조건에 어긋났다.

시도해본 테스트케이스

3
1 0 0
0 0 0
9 0 1
> 결과: 6
이 테스트 케이스로 잘못된 원인을 파악할 수 있었다