백준 16236 아기 상어

작성일 | In |

Problem : 아기 상어

유형 : BFS

문제 해석

  • 아기 상어를 조건에 맞춰 움직이며, 가장 가까운 물고기를 먹는다.
  • 물고기를 먹은 개수에 따라서 아기 상어는 커진다.
  • 물고기를 더 이상 먹지 못하면 지금까지 이동한 거리를 출력한다.

문제 재해석

  • 최단 거리를 찾아야 하므로 BFS를 통해 움직여야 한다.
  • 가장 위쪽, 가장 왼쪽을 찾아야 하므로 정렬이 필요하다.

해결 전략 (17)

  • BFS를 이용하여 아기 상어를 움직인다.
  • 가장 가까운 거리에 있는 물고기들의 목록을 저장한다.
  • 해당 물고기 목록 중 가장 위쪽 왼쪽에 있는 물고기를 선택한다.
  • 해당 물고기를 먹는다.

설계, 구현 (30)

  • 먹을 수 있는 가장 가까운 물고기들의 목록을 담는 벡터를 만든다.
  • 상어는 가려는 곳이 물이거나, 물고기가 자신의 크기와 같으면 이동만 한다.
  • BFS를 돌다가 물고기를 먹는 순간, 다음 단계의 BFS는 진행하지 않는다.
    • 하지만 현재 단계의 남은 과정들은 진행해야 한다.

주의할 점

  • 물고기를 먹고 난 뒤, 상어의 위치는 바뀌어야 한다.
  • 상어의 위치에 크기가 9인 물고기가 있는 것이 아니다.

디버깅 (3)

  • 아기 상어의 초기 위치를 크기가 9인 물고기가 있는것으로 잘못 설정하였다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
#define pp pair<int, int>
#define x first
#define y second

using namespace std;

bool visit[22][22];
int water[22][22];

vector<pp> fish_vec;


int n;
int shark_size = 2;
int _time, ate_fish_cnt;
int shark_x, shark_y;

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

void Init() {
    fish_vec.clear();
    memset(visit, false, sizeof(visit));
}

void eat_fish() {
    sort(fish_vec.begin(), fish_vec.end());

    int fx = fish_vec[0].x;
    int fy = fish_vec[0].y;

    water[fx][fy] = 0;
    shark_x = fx;
    shark_y = fy;

    ate_fish_cnt++;


    if (ate_fish_cnt == shark_size) {
        shark_size++;
        ate_fish_cnt = 0;
    }

}

bool is_ate() {
    int dist = 0;
    bool ate = false;

    queue<pp> q;

    visit[shark_x][shark_y] = true;
    q.push({ shark_x,shark_y });

    while (!q.empty()) {
        int q_size = q.size();
        dist++;

		while (q_size--) {
            auto cur = q.front(); q.pop();

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

                if (nx < 0 or nx >= n or ny < 0 or ny >= n) continue;
                if (visit[nx][ny]) continue;
                if (water[nx][ny] > shark_size) continue;

                visit[nx][ny] = true;
                q.push({ nx,ny });

                if (shark_size == water[nx][ny] or water[nx][ny] == 0)continue;
                fish_vec.push_back({ nx,ny });
                ate = true;
            }
		}
        if (ate) {
            _time += dist;
            return true;
        }
    }


    return false;
}

int solve() {
    while (1) {
        if (!is_ate())   return _time;
        eat_fish();
        Init();
    }
}

void input() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii) {
            cin >> water[i][ii];
            if (water[i][ii] == 9) {
                water[i][ii] = 0;
                shark_x = i;
                shark_y = ii;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    input();
    cout << solve() << "\n";


    return 0;
}

피드백

  • 초기 상태가 변경되는 경우를 신경 쓰자.