아기 상어

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 16449 6615 3776 36.991%

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

풀이

bfs + 시뮬레이션인 것 같다.

풀이

  1. 2차원 배열을 통해 입력을 받는다.
  2. 상어가 존재하는 9일 경우, 상어의 위치를 저장한다. 그리고 이후에 bfs 탐색을 하면서 조건을 검사하기 위해 상어가 있던 위치는 0으로 바꿔준다.
  3. 최초의 shark 객체를 상어의 위치와 distance 0으로 만들어준다. size = count = 2이다. 초기 상어의 크기가 2이기 때문이다.
  4. 상어가 가장 가까운 물고리를 찾기 위해서 bfs 를 시작한다. 초기에 상어를 큐에 넣어준다. 상어의 distance는 INF 값으로 할당한다. 이유는 최단 거리를 찾아서 업데이트 할 것이기 때문!
  5. 큐에서 상어를 네 방향을 탐색한다. 범위를 벗어나지 않고, 방문한 적이 없는 곳을 큐에 넣는다.
  6. 5번을 반복하면 큐에 여러 값들이 들어가므로 조건 검사를 제대로 할 수 있게 된다.
  7. 조건을 검사한다.
    • 상어의 distance에는 최단 거리가 담기는데, 현재 위치의 거리가 더 크다면? 이때는 bfs를 중단한다. 최단 거리보다 더 움직인 것이기 때문에 최단 거리는 구해졌다.
    • 상어의 크기인 size 보다 큰 물고기는 먹을 수 없으므로 다음 물고기를 확인하기 위해 skip 한다.
    • 물고기가 존재하면서, 상어의 크기보다 작은 물고기인 경우에는 상어가 먹을 수 있다.
      • 상어가 이 물고기까지 온 거리가 그 전에 알고 있던 거리보다 작다면 최단 거리로 갱신한다.
      • 그렇지 않고 이 물고기까지 온 거리와 그 전에 알고 있던 거리가 같다면 더 위에 있는 물고기를 먹는다.
      • 그러한 물고기가 여러 마리라면 더 왼쪽에 있는 물고기를 먹는다.
      • 물고기를 먹는 것은 상어가 그 물고기가 있는 곳에 위치하는 것으로 먼저 표현을 한다.
  8. bfs 탐색이 끝나고 나서 상어의 distance 가 바뀌었는지 확인한다. 바뀌었다면, 상어의 위치가 바뀌고 distance 값도 바뀌었다. 이는 상어가 그 물고기의 위치를 찾아서 먹었음을 의미한다.
  9. 상어가 물고기를 먹으러 이동한 거리를 time에 더하고, count 값을 감소시킨다. 이는 상어가 자신의 크기만큼 물고기를 먹기 위함이다.
  10. count == 0인 경우를 확인한다. true 라면 상어가 자신의 크기만큼 물고기를 다 먹었고 상어의 크기는 1 증가한다. 그리고 count는 size로 초기화 해준다.
  11. 8번의 조건을 확인하면서 상어의 distance 값이 바뀌지 않았다면, 상어가 물고기를 먹을 수 있는 물고기를 찾지 못해 bfs가 그대로 종료됐음을 의미한다. 따라서 반복문을 빠져나온다.
  12. time 값을 반환한다.

[Code]

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
package SW_Study;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

/**
* created by victory_woo on 2020/04/15
* 아기 상어.
* 시뮬레이션 + bfs
* 난이도 높음... 어려움...
* 다시 풀어보기!
*/
public class Problem16236 {
private static final int INF = Integer.MAX_VALUE;
private static int n;
private static int[][] map;

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = toInt(br.readLine());

map = new int[20][20];

// 상어의 위치를 저장하기 위한 변수를 선언한다.
int sharkX = 0, sharkY = 0;

for (int i = 0; i < n; i++) {
String[] in = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
map[i][j] = toInt(in[j]);
// 상어의 위치를 저장한다.
if (map[i][j] == 9) {
sharkX = i;
sharkY = j;

// 상어가 이동할 때, 최초 상어의 위치는 중요하지 않기 때문에
// 상어가 최초 위치했던 곳은 빈곳으로 바꿔준다.
map[i][j] = 0;
}
}
}
System.out.println(solve(sharkX, sharkY));
}

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

private static int solve(int x, int y) {
int time = 0; // 이동하는 데 걸리는 시간.
int size = 2; // 상어의 크기. 이동할 때마다 상어의 크기와 비교해야 함.
int count = size;
Fish shark = new Fish(x, y, 0);
// 최단 거리를 찾아야 하기 때문에 최초 위치는 상어의 위치로 시작한다.

// 상어가 가장 가까운 물고기를 찾기 위해서 bfs 탐색을 한다.
while (true) {

// 방문 여부 체크.
boolean[][] visit = new boolean[20][20];
LinkedList<Fish> q = new LinkedList<>();
visit[shark.x][shark.y] = true;
q.add(new Fish(shark.x, shark.y, 0));
shark.distance = INF;

while (!q.isEmpty()) {
Fish cur = q.remove();

// 계속 진행하다 보면 현재 위치의 거리가 우리가 찾은 최단 거리보다 커지는 경우가 존재한다.
// bfs 탐색을 중단한다.
// 거리가 최단 거리보다 멀어졌다는 의미는 더이상 확인할 물고기가 없다는 걸 뜻한다.
if (cur.distance > shark.distance) break;

// 상어의 크기보다 큰 물고기가 있다면 해당 물고기는 skip 한다. 즉, 건너뛰고 다른 물고기를 탐색한다.
if (map[cur.x][cur.y] > size) continue;

// 물고기가 존재하고, 현재 상어보다 물고기의 크기가 작다고 하면 먹을 수 있다.
if (map[cur.x][cur.y] != 0 && map[cur.x][cur.y] < size) {
// 이 물고기까지 온 거리가 그 전에 알고 있던 거리보다 작다면 최단 거리를 갱신한다.
// shark 를 현재 위치로 바꿔준다.
if (cur.distance < shark.distance) {
shark = cur;
} else if (cur.distance == shark.distance) {
// 거리가 같은 물고기가 존재한다면
// 더 위에 있는 물고기를 먹는다.
if (cur.x < shark.x) {
shark = cur;
} else if (cur.x == shark.x && cur.y < shark.y) {
// 같은 높이에 있다면 더 왼쪽에 있는 물고기를 먹어야 한다.
// 따라서 y 좌표가 더 작은 물고기를 먹는다.
shark = cur;
}
}
// 가장 가까운 물고기를 찾았기 때문에 continue 로 아래 네 방향으로 진행하는 탐색을 skip 한다.
continue;
}

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

if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (visit[nx][ny]) continue;

visit[nx][ny] = true;
q.add(new Fish(nx, ny, cur.distance + 1));
}
}

// INF 가 아닌 경우 물고기를 찾은 경우.
// 이동 거리르 증가하고, 물고기의 갯수를 줄여준다.
if (shark.distance != INF) {
time += shark.distance;
count--;
if (count == 0) {
size++;
count = size;
}

// 먹은 물고기는 0으로 지워준다.
map[shark.x][shark.y] = 0;

} else {
break;
}
}

return time;
}


private static int toInt(String value) {
return Integer.parseInt(value);
}

static class Fish {
int x;
int y;
int distance; // 상어가 이동하는 데 걸린 거리.(거리가 곧 시간)

Fish(int x, int y, int distance) {
this.x = x;
this.y = y;
this.distance = distance;
}
}
}