백준 16236번 : 아기 상어
n 크기의 아기상어가 있어 이 아기상어가 n*n 만큼 크기의 공간 내의 물고기를 잡아 먹는데에 걸리는 시간을 리턴하는 문제이다.
여기서 조건이 꽤 까다롭다.
- 아기 상어의 초기 크기는 2이고 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1씩 증가한다.
- 더 이상 먹을 수 있는 물고기가 없다면 종료된다.
- 공간 내에 먹을 수 있는 물고기가 1마리보다 많다면 거리가 가장 가까운 물고기부터 먹는다.
- 거리가 가장 가까운 물고기가 많다면 가장 위에 있는 물고기, 해당 물고기가 여러 마리라면 가장 왼쪽에 있는 물고기부터 먹는다.
- 아기 상어는 이동시 한 칸에 1초가 걸린다. 단, 물고기를 먹는 행위는 시간을 소모하지 않는다.
공간의 상태는
0 : 빈칸
1~6 : 물고기의 크기
9 : 아기 상어의 위치
로 이루어져있다.
처음 이 문제를 풀 때, 9도 물고기의 크기인 줄 알고 엄청 해멨다.
사실 이걸 알았어도 깔끔하게 풀지는 못했을 것 같다.
전체적인 로직은 BFS 탐색을 통해 구현했다.
우선 point 클래스를 구현했는데, 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Point implements Comparable<Point> {
int x, y, dist;
public Point(int x, int y, int dist) {
this.x = x;
this.y = y;
this.dist = dist;
}
@Override
public int compareTo(Point other) {
if (this.dist == other.dist) {
if (this.x == other.x) {
return Integer.compare(this.y, other.y);
} else {
return Integer.compare(this.x, other.x);
}
} else {
return Integer.compare(this.dist, other.dist);
}
}
}
이 Point 클래스는 아기 상어의 위치(x,y)와 그 위치까지의 거리(dist)를 저장하는 클래스이다.
Comparable 인터페이스를 구현한 구현체이기도 한데, 이는 먹이가 될 물고기들의 크기를 비교할 수 있도록 하기 위함이다.
compareTo 메소드를 오버라이드하여 물고기들 사이의 순서를 정의했다.
다음은 main 함수인데,
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
public class Main {
static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
static int[][] arr;
static int n, x, y, size = 2, count = 0, time = 0;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 9) {
x = i;
y = j;
arr[i][j] = 0;
}
}
}
while (true) {
Point p = bfs();
if (p == null) break;
time += p.dist;
count++;
if (count == size) {
size++;
count = 0;
}
arr[p.x][p.y] = 0;
x = p.x;
y = p.y;
}
System.out.println(time);
}
}
그 전에 Main 클래스부터 보면, dx, dy는 탐색의 방향을 설정하기 위한 배열이고, arr은 n*n의 공간을, size, count, time은 각각 아기 상어의 크기, 먹은 횟수, 이동 시간을 의미한다.
이때 count가 size와 같아지면 size가 1씩 증가하고 count가 0으로 다시 초기화된다.
맨 처음 size가 2로 초기화되는 이유는 문제에서 주어진 상어의 초기 크기가 2이기 때문이다.
이제 main 함수를 보면, 가장 먼저 입력 받은 맵 크기 n과 맵의 정보를 arr에 저장한다. 여기서 아기 상어의 초기 위치인 (x,y)를 찾아서 저장하고 맵 상에서는 아기 상어의 위치를 0으로 변경한다.
다음으로 아기 상어가 먹이를 찾는 과정을 시작한다. 이 과정은 아기 상어가 먹을 수 있는 물고기가 없을 떄까지 반복된다.
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
static Point bfs() {
boolean[][] visited = new boolean[n][n];
Queue<Point> q = new LinkedList<>();
List<Point> fishes = new ArrayList<>();
visited[x][y] = true;
q.offer(new Point(x, y, 0));
while (!q.isEmpty()) {
Point cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx >= n || ny >= n || nx < 0 || ny < 0) {
continue;
}
if (visited[nx][ny] || arr[nx][ny] > size) {
continue;
}
visited[nx][ny] = true;
q.offer(new Point(nx, ny, cur.dist + 1));
if (arr[nx][ny] > 0 && arr[nx][ny] < size) {
fishes.add(new Point(nx, ny, cur.dist + 1));
}
}
}
return fishes.isEmpty() ? null : Collections.min(fishes);
}
bfs 과정에서 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸으로는 이동할 수 없고, 자신의 크기보다 작은 물고기만 먹을 수 있다는 것을 기억해야한다.
그러므로, BFS과정에서 자신 보다 큰 물고기가 있는 칸은 방문하지 않고, 자신의 크기보다 작은 물고기가 있는 칸을 발견하면 그 위치를 먹이 후보 리스트인 fishes에 추가한다.
이 과정이 끝나면 먹이 후보 리스트에서 가장 가까운 물고기를 선택한다. 이 때 Collections.min 함수를 사용하여 가장 가까운 물고기를 찾고, 이 함수는 Point 클래스에서 정의한 compareTo 메소드를 사용한다.
다시 메인 함수로 돌아와
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while (true) {
Point p = bfs();
if (p == null) break;
time += p.dist;
count++;
if (count == size) {
size++;
count = 0;
}
arr[p.x][p.y] = 0;
x = p.x;
y = p.y;
}
System.out.println(time);
bfs의 결과를 Point 타입의 p 변수에 저장한다.
또한 time에 먹이까지 가는 시간을 저장한다.
이 p 변수에는 가장 가까운 물고기가 선택되었고, 이 물고기를 먹고 아기 상어는 count를 증가시키고, 먹이를 먹은 횟수가 아기 상어의 크기와 같아지면 아기 상어의 크기를 1 증가시킨 다음 횟수를 0으로 초기화한다.
이후 아기 상어의 위치에는 물고기가 없으므로 0으로 초기화하고 해당 위치를 다시 (x,y)에 저장한다.
이와 같은 과정을 반복하게되면 만약 더 이상 먹을 물고기가 없다면 bfs는 null을 반환하게 되고 이 결과가 p 변수에 저장되며, p에 null이 저장된다면 탐색 과정은 종료된다.
마지막으로 중첩된 시간, time을 리턴하면 된다.
전체 소스 코드는 다음과 같다.
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Point implements Comparable<Point> {
int x, y, dist;
public Point(int x, int y, int dist) {
this.x = x;
this.y = y;
this.dist = dist;
}
@Override
public int compareTo(Point other) {
if (this.dist == other.dist) {
if (this.x == other.x) {
return Integer.compare(this.y, other.y);
} else {
return Integer.compare(this.x, other.x);
}
} else {
return Integer.compare(this.dist, other.dist);
}
}
}
public class Main {
static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
static int[][] arr;
static int n, x, y, size = 2, count = 0, time = 0;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 9) {
x = i;
y = j;
arr[i][j] = 0;
}
}
}
while (true) {
Point p = bfs();
if (p == null) break;
time += p.dist;
count++;
if (count == size) {
size++;
count = 0;
}
arr[p.x][p.y] = 0;
x = p.x;
y = p.y;
}
System.out.println(time);
}
static Point bfs() {
boolean[][] visited = new boolean[n][n];
Queue<Point> q = new LinkedList<>();
List<Point> fishes = new ArrayList<>();
visited[x][y] = true;
q.offer(new Point(x, y, 0));
while (!q.isEmpty()) {
Point cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx >= n || ny >= n || nx < 0 || ny < 0) {
continue;
}
if (visited[nx][ny] || arr[nx][ny] > size) {
continue;
}
visited[nx][ny] = true;
q.offer(new Point(nx, ny, cur.dist + 1));
if (arr[nx][ny] > 0 && arr[nx][ny] < size) {
fishes.add(new Point(nx, ny, cur.dist + 1));
}
}
}
return fishes.isEmpty() ? null : Collections.min(fishes);
}
}
처음에는 문제 조건이 별거 없는 줄 알고 기본적인 탐색 문제인가싶어 간단하게 풀었는데, 전혀 다른 결과값이 나와서 조건을 여러 번 정독했다.
특히 9가 아기 상어의 위치인 것을 모르고 진행하여 로직이 완전 꼬였었다.
이후에는 이 거리에 대한 시간과 탐색을 어떤 방식으로 진행해야하는지 헷갈리고 어려워 답안 참고를 많이했는데, 그래도 여전히 어렵다.
완벽히 이해는 못했더라도 다음에 비슷한 문제를 만난다면 참고하기 위해 기록한다.