16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
상어가 지나갈 수 있는 경우는
1. 자신의 크기보다 작거나 같은 물고기가 있는 경우
2. 빈 칸
이렇게 두 가지이며, 상어는 자신보다 작은 물고기만 먹을 수 있습니다.
그리고 자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 커집니다.
상어가 먹을 수 있는 물고기를 bfs로 찾고,
먹을 수 있는 물고기가 여러마리면 그 중 가장 가까운 물고기, 가장 위에 있는 물고기, 가장 왼쪽에 있는 물고기 순으로 먹습니다.
저는 bfs로 순회하며 먹을 수 있는 물고기를 ArrayList에 담았고 위의 조건 순으로 정렬하였습니다.
그럼 0번 인덱스에 있는 물고기를 먹으면 되고, 그 물고기까지의 거리를 ans에 더해주고, 그 위치에서 다시 시작합니다.
위의 과정을 물고기를 먹을 수 있을때까지 반복해줍니다.
[C++]
|
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
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
queue<pair<int, int> > q;
int list[21][21];
bool visit[21][21];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, ans;
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first < b.first) return true;
else if (a.first == b.first) {
if (a.second < b.second) return true;
else return false;
}
else return false;
}
void bfs() {
int ssize = 2;
int eat = 0;
while (1) {
bool chk = false;
vector<pair<int, int> > v;
for (int t = 1; ; t++) {
int qsize = q.size();
while (qsize--) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (visit[nx][ny]) continue;
if (list[nx][ny] > ssize) continue;
if (list[nx][ny] && list[nx][ny] < ssize) {
v.push_back({ nx,ny });
}
q.push({ nx,ny });
visit[nx][ny] = true;
}
}
if (!v.empty()) {
ans += t;
break;
}
if (q.empty()) {
chk = true;
break;
}
}
if (chk) break;
sort(v.begin(), v.end(), cmp);
int x = v[0].first;
int y = v[0].second;
list[x][y] = 0;
eat++;
if (eat == ssize) {
ssize++;
eat = 0;
}
v.clear();
memset(visit, false, sizeof(visit));
while (!q.empty()) q.pop();
q.push({ x,y });
visit[x][y] = true;
}
cout << ans << '\n';
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> list[i][j];
if (list[i][j] == 9) {
q.push({ i,j });
visit[i][j] = true;
list[i][j] = 0;
}
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
bfs();
return 0;
}
|
cs |
[Java]
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 | import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.Deque; import java.util.StringTokenizer; import java.io.BufferedReader; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static Deque<int[]> dq = new ArrayDeque<>(); static int list[][] = new int[21][21]; static boolean visit[][] = new boolean[21][21]; static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; static int N, ans; static void bfs() { int size = 2; int eat = 0; while (true) { boolean chk = false; ArrayList<int[]> eatlist = new ArrayList<>(); for (int t = 1;; t++) { int qsize = dq.size(); while (qsize-- > 0) { int x = dq.peek()[0]; int y = dq.poll()[1]; for (int i = 0; i < 4; i++) { int nx = x + direct[i][0]; int ny = y + direct[i][1]; if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue; if (visit[nx][ny]) continue; if (list[nx][ny] > size) continue; if (list[nx][ny] != 0 && list[nx][ny] < size) { eatlist.add(new int[] { nx, ny }); } dq.add(new int[] { nx, ny }); visit[nx][ny] = true; } } if (!eatlist.isEmpty()) { ans += t; break; } if (dq.isEmpty()) { chk = true; break; } } if (chk) break; Collections.sort(eatlist, new Comparator<int[]>() { @Override public int compare(int[] a, int[] b) { if (a[0] == b[0]) return a[1] - b[1]; else return a[0] - b[0]; } }); int x = eatlist.get(0)[0]; int y = eatlist.get(0)[1]; list[x][y] = 0; eat++; if (eat == size) { eat = 0; size++; } dq.clear(); eatlist.clear(); for (int i = 0; i < N; i++) Arrays.fill(visit[i], false); dq.add(new int[] { x, y }); visit[x][y] = true; } System.out.println(ans); } static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < N; j++) { list[i][j] = Integer.parseInt(st.nextToken()); if (list[i][j] == 9) { list[i][j] = 0; dq.add(new int[] { i, j }); visit[i][j] = true; } } } } public static void main(String[] args) throws Exception { input(); bfs(); } } | cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 7576 토마토 (0) | 2021.02.19 |
|---|---|
| boj 17135 캐슬 디펜스 (0) | 2021.02.17 |
| boj 10026 적록색약 (0) | 2021.02.13 |
| boj 2206 벽 부수고 이동하기 (0) | 2021.02.13 |
| boj 14502 연구소 (0) | 2021.02.12 |