[백준] 16236번 - 아기 상어 (Gold 3)
업데이트:
문제 링크
문제 설명
아기 상어가 다음 조건처럼 움직인다고 하자.
- 아기 상어가 먹을 수 있는 물고기는 자기 크기보다 작은 물고기이다.
- 아기 상어가 지나갈 수 있는 위치는 빈칸 또는 자기 크기 이하의 물고기가 있는 칸이다.
- 한 칸 이동에는 1초가 필요하고, 물고기를 먹는데는 시간이 필요하지 않다.
- 아기 상어는 먹을 수 있는 가장 가까운 물고기 중 가장 위쪽에 있으면서 가장 왼쪽에 있는 물고기를 먹는다.
- 아기 상어가 크기만큼 물고기를 잡아먹으면 크기가 1 커진다.
이 때, 아기 상어가 물고기를 더 이상 잡아먹을 수 없을 때까지 걸리는 시간을 구하면 된다.
정답 코드 및 설명
아기 상어가 먹을 수 있는 가장 가까운 물고기를 BFS로 찾는다.
이웃한 칸 중 빈 칸 또는 현재 아기 상어의 크기 이하의 물고기가 있는 칸만을 연결된 것으로 간주하면 된다.
이 때, 같은 거리에 있는 물고기를 모두 찾아주어야 함에 주의한다.
처음에는 위쪽-왼쪽 순으로 탐색하는 식의 꼼수가 먹히지 않을까 생각했었는데, 거리가 2 이상만 되어도 불가능하다.
아기 상어가 먹을 수 있는 가장 가까운 물고기들을 찾았으면, 무엇을 먹을지를 정한다.
물고기를 먹은 자리는 빈 칸으로 만들어야하고, 물고기를 먹었으면 크기 정보를 업데이트 해주어야 한다.
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
import java.io.*;
import java.util.*;
public class Main {
static int[] xAdd = { -1, 0, 0, 1 }, yAdd = { 0, -1, 1, 0 };
static int[][] space;
static int n;
static Shark shark;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
space = new int[n][n];
// 처음 상태
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int fish = Integer.parseInt(st.nextToken());
// 아기 상어의 위치는 0으로 둔다
if (fish == 9)
shark = new Shark(i, j);
if (fish != 9)
space[i][j] = fish;
}
}
bw.write(total() + "");
bw.close();
}
// 전체 시간 구하기
static int total() {
int totalTime = 0;
while (true) {
int time = move();
// 더 이상 물고기를 잡아먹을 수 없는 경우
if (time == -1)
break;
totalTime += time;
}
return totalTime;
}
// 물고기를 잡아먹는데 드는 시간 구하기(더 이상 잡아먹을 수 없으면 -1 리턴)
// BFS를 활용한다
static int move() {
int[][] dist = new int[n][n];
boolean[][] check = new boolean[n][n];
Queue<int[]> queue = new LinkedList<>();
ArrayList<int[]> candidate = new ArrayList<>();
int x = shark.x, y = shark.y;
queue.add(new int[] { x, y });
check[x][y] = true;
int maxDist = 0;
// BFS
while (!queue.isEmpty()) {
int[] curr = queue.poll();
for (int i = 0; i < 4; i++) {
int newX = curr[0] + xAdd[i];
int newY = curr[1] + yAdd[i];
if (isAble(newX, newY) && !check[newX][newY]) {
check[newX][newY] = true;
// 이동할 수 있는 칸인 경우
if (shark.size >= space[newX][newY]) {
queue.add(new int[] { newX, newY });
dist[newX][newY] = dist[curr[0]][curr[1]] + 1;
// 현재 이동한 칸 수 체크
if (maxDist < dist[newX][newY]) {
// 이미 먹을 수 있는 물고기가 있는 거리를 지나친 경우
if (!candidate.isEmpty()) {
shark.eat(candidate);
space[shark.x][shark.y] = 0;
return maxDist;
}
maxDist++;
}
// 먹을 수 있는 물고기 정보를 candidate에 넣는다
if (shark.size > space[newX][newY] && space[newX][newY] != 0) {
candidate.add(new int[] { newX, newY });
}
}
}
}
}
// 물고기를 먹은 경우 그 자리를 빈 칸으로 만든다
if (!candidate.isEmpty()) {
shark.eat(candidate);
space[shark.x][shark.y] = 0;
return maxDist;
}
// 아무 것도 먹을 수 없는 경우
return -1;
}
// 범위 안에 있는지 확인
static boolean isAble(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
}
class Shark {
int x, y, size, curr;
// 처음 아기 상어의 상태
Shark(int x, int y) {
this.x = x;
this.y = y;
this.size = 2;
this.curr = 0;
}
// 아기 상어가 물고기를 잡아 먹음
// candidate : 잡아먹을 수 있는 물고기의 위치들
void eat(ArrayList<int[]> candidate) {
this.x = candidate.get(0)[0];
this.y = candidate.get(0)[1];
for (int i = 1; i < candidate.size(); i++) {
// 가장 위쪽의 물고기 고르기
if (this.x > candidate.get(i)[0]) {
this.x = candidate.get(i)[0];
this.y = candidate.get(i)[1];
}
// 가장 왼쪽의 물고기 고르기
if (this.x == candidate.get(i)[0] && this.y > candidate.get(i)[1])
this.y = candidate.get(i)[1];
}
this.curr++;
// 크기가 1 커져야하는 경우
if (this.curr == this.size) {
this.curr = 0;
this.size++;
}
}
}
댓글남기기