백준 16236번 (아기 상어, C++, Simulation) [BAEKJOON]
문제
https://www.acmicpc.net/problem/16236
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 52413 | 23961 | 14308 | 42.311% |
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: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.
출력
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.
예제 입력 1
plaintext
3
0 0 0
0 0 0
0 9 0예제 출력 1
plaintext
0예제 입력 2
plaintext
3
0 0 1
0 0 0
0 9 0예제 출력 2
plaintext
3예제 입력 3
plaintext
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4예제 출력 3
plaintext
14예제 입력 4
plaintext
6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6예제 출력 4
plaintext
60예제 입력 5
plaintext
6
6 0 6 0 6 1
0 0 0 0 0 2
2 3 4 5 6 6
0 0 0 0 0 2
0 2 0 0 0 0
3 9 3 0 0 1예제 출력 5
plaintext
48예제 입력 6
plaintext
6
1 1 1 1 1 1
2 2 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
0 0 0 0 0 6
0 0 0 0 0 9예제 출력 6
plaintext
39알고리즘 분류
문제의 조건을 이해 못해서 해결하는데 엄청 시간이 걸렸다.
특히 맵에 먹을 수 있는 물고기가 여러 마리 일때 조건에서 막혔는데
예제와 글을 계속 읽어보면서 겨우 이해했다.
결론은 거리가 가장 가까운 물고기들 중에서 가장 위쪽에 있으면서 좌측에 있는 물고기를 픽하는 것
이 문제의 설명이 너무 잘되어있는 글이 있어서 첨부한다.
위의 설명을 구현하기 위해서
- 상어의 위치에서 BFS 탐색을 통하여 상어가 먹을 수 있는 가장 가까운 물고기의 위치를 저장한다.
(탐색의 방향은 상/좌/우/하)
상어가 먹을 수 있는 물고기의 위치에서 가장 위쪽에 있으면서 좌측에 있는 물고기를 선택한다.
해당 물고기의 위치로 상어를 옮기고 물고기를 제거하며 상어의 크기를 업데이트 해준다.
해당 위치까지 얼마나 걸렸는지 카운트 해준다.
상어가 먹을 수 있는 물고기가 없을 때까지 1 - 4 를 반복한다.
출처
통과된 코드
cpp
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
// 최대 범위
constexpr int MAX = 20;
// 상/좌/우/하
int dxdy[4][2] = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };
pair<int, int> Shark; // 상어 크기, 경험치?
tuple<int, int, int> posShark; // 상어의 x, y위치 / 시간
tuple<int, int, int> tempT;
int N, dx, dy;
int map[MAX][MAX]; // 맵
bool eatMap[MAX][MAX]; // 먹을 수 있는 물고기 체크
bool mapCheck[MAX][MAX]; // BFS 방문 체크에 사용
// BFS 탐색, 반환값음 상어의 위치와 시간
tuple<int, int, int> SharkBFS()
{
queue<tuple<int, int, int>> myQ;
// 방문처리 초기화
fill(&mapCheck[0][0], &mapCheck[N - 1][N], false);
fill(&eatMap[0][0], &eatMap[N - 1][N], false);
myQ.push(posShark);
mapCheck[get<0>(posShark)][get<1>(posShark)] = true;
int dis = 99999;
while (!myQ.empty()) {
tempT = myQ.front();
myQ.pop();
// 상/하/좌/우를 탐색하기 위한 반복문
for (int i = 0; i < 4; i++) {
dx = get<0>(tempT) + dxdy[i][0];
dy = get<1>(tempT) + dxdy[i][1];
// 문제의 범위를 벗어나는 경우 => 넘어간다.
if (dx < 0 || dy < 0 || dx >= N || dy >= N) continue;
// 이미 방문한 곳 일 경우와 해당 칸의 물고기가 상어보다 클 경우 => 넘어간다.
if (mapCheck[dx][dy] == true || map[dx][dy] > Shark.first) continue;
// 상어가 더 크고, 빈 공간이 아니라면
if (map[dx][dy] < Shark.first && map[dx][dy] != 0 ) {
if (get<2>(tempT) + 1 <= dis) {
eatMap[dx][dy] = true;
dis = get<2>(tempT) + 1;
}
}
mapCheck[dx][dy] = true; // 방문처리
myQ.push(make_tuple(dx, dy, get<2>(tempT) + 1)); // 탐색 Q에 넣기
}
}
// 먹을 수 있는 물고기들 중에서
// 가장 위, 좌측에 있는 물고기를 선택한다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (eatMap[i][j] == true) {
Shark.second++;
map[i][j] = 0;
if (Shark.first == Shark.second) {
Shark.first++;
Shark.second = 0;
}
return make_tuple(i, j, dis);
}
}
}
// 없다면 기존 상어의 위치를 반환한다.
return posShark;
}
int main()
{
ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
cin.tie(NULL);
cout.tie(NULL);
Shark = make_pair(2, 0);
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
if (map[i][j] == 9) { // 상어의 위치를 저장
posShark = make_tuple(i, j, 0);
map[i][j] = 0;
}
}
}
bool check = true;
while (check) {
check = false;
for (int i = 0; i < N && !check; i++) {
for (int j = 0; j < N && !check; i++) {
if (map[i][j] >= 1) check = true;
}
}
tempT = SharkBFS();
// BFS 탐색 후에도 상어의 움직임이 없다면 먹을 수 있는 물고기가 없다.
if (get<2>(tempT) == get<2>(posShark)) break;
else posShark = tempT;
}
cout << get<2>(posShark);
return 0;
}
디버깅
https://www.acmicpc.net/board/view/100687
예제 입력 4
여기서부터는 시뮬레이션이 매우 길기 때문에 디버깅 출력으로 대신하겠습니다.
또한, 가독성을 위해 상어의 위치는 9 대신 "■", 물고기가 없는 위치는 0 대신 "." 로 표기했습니다.
plaintext
5 4 3 2 3 4
4 3 2 3 4 5
3 2 ■ 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6
0s / Lv. 2 (Exp 0 / 2)
5 4 3 2 3 4
4 3 2 3 4 5
3 2 . 5 6 6
2 ■ 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6
2s / Lv. 2 (Exp 1 / 2)
5 4 3 2 3 4
4 3 2 3 4 5
3 2 . 5 6 6
2 . 2 3 4 5
3 2 ■ 6 5 4
6 6 6 6 6 6
4s / Lv. 3 (Exp 0 / 3)
5 4 3 2 3 4
4 3 2 3 4 5
3 2 . 5 6 6
2 . ■ 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
5s / Lv. 3 (Exp 1 / 3)
5 4 3 2 3 4
4 3 ■ 3 4 5
3 2 . 5 6 6
2 . . 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
7s / Lv. 3 (Exp 2 / 3)
5 4 3 ■ 3 4
4 3 . 3 4 5
3 2 . 5 6 6
2 . . 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
9s / Lv. 4 (Exp 0 / 4)
5 4 ■ . 3 4
4 3 . 3 4 5
3 2 . 5 6 6
2 . . 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
10s / Lv. 4 (Exp 1 / 4)
5 4 . . ■ 4
4 3 . 3 4 5
3 2 . 5 6 6
2 . . 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
12s / Lv. 4 (Exp 2 / 4)
5 4 . . . 4
4 3 . ■ 4 5
3 2 . 5 6 6
2 . . 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
14s / Lv. 4 (Exp 3 / 4)
5 4 . . . 4
4 ■ . . 4 5
3 2 . 5 6 6
2 . . 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
16s / Lv. 5 (Exp 0 / 5)
5 ■ . . . 4
4 . . . 4 5
3 2 . 5 6 6
2 . . 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
17s / Lv. 5 (Exp 1 / 5)
5 . . . . 4
■ . . . 4 5
3 2 . 5 6 6
2 . . 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
19s / Lv. 5 (Exp 2 / 5)
5 . . . . 4
. . . . 4 5
■ 2 . 5 6 6
2 . . 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
20s / Lv. 5 (Exp 3 / 5)
5 . . . . 4
. . . . 4 5
. ■ . 5 6 6
2 . . 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
21s / Lv. 5 (Exp 4 / 5)
5 . . . . 4
. . . . 4 5
. . . 5 6 6
■ . . 3 4 5
3 2 . 6 5 4
6 6 6 6 6 6
23s / Lv. 6 (Exp 0 / 6)
5 . . . . 4
. . . . 4 5
. . . 5 6 6
. . . 3 4 5
■ 2 . 6 5 4
6 6 6 6 6 6
24s / Lv. 6 (Exp 1 / 6)
5 . . . . 4
. . . . 4 5
. . . 5 6 6
. . . 3 4 5
. ■ . 6 5 4
6 6 6 6 6 6
25s / Lv. 6 (Exp 2 / 6)
5 . . . . 4
. . . . 4 5
. . . 5 6 6
. . . ■ 4 5
. . . 6 5 4
6 6 6 6 6 6
28s / Lv. 6 (Exp 3 / 6)
5 . . . . 4
. . . . 4 5
. . . ■ 6 6
. . . . 4 5
. . . 6 5 4
6 6 6 6 6 6
29s / Lv. 6 (Exp 4 / 6)
5 . . . . 4
. . . . ■ 5
. . . . 6 6
. . . . 4 5
. . . 6 5 4
6 6 6 6 6 6
31s / Lv. 6 (Exp 5 / 6)
5 . . . . 4
. . . . . ■
. . . . 6 6
. . . . 4 5
. . . 6 5 4
6 6 6 6 6 6
32s / Lv. 7 (Exp 0 / 7)
5 . . . . ■
. . . . . .
. . . . 6 6
. . . . 4 5
. . . 6 5 4
6 6 6 6 6 6
33s / Lv. 7 (Exp 1 / 7)
5 . . . . .
. . . . . .
. . . . 6 ■
. . . . 4 5
. . . 6 5 4
6 6 6 6 6 6
35s / Lv. 7 (Exp 2 / 7)
5 . . . . .
. . . . . .
. . . . ■ .
. . . . 4 5
. . . 6 5 4
6 6 6 6 6 6
36s / Lv. 7 (Exp 3 / 7)
5 . . . . .
. . . . . .
. . . . . .
. . . . ■ 5
. . . 6 5 4
6 6 6 6 6 6
37s / Lv. 7 (Exp 4 / 7)
5 . . . . .
. . . . . .
. . . . . .
. . . . . ■
. . . 6 5 4
6 6 6 6 6 6
38s / Lv. 7 (Exp 5 / 7)
5 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . 6 5 ■
6 6 6 6 6 6
39s / Lv. 7 (Exp 6 / 7)
5 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . 6 ■ .
6 6 6 6 6 6
40s / Lv. 8 (Exp 0 / 8)
5 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . ■ . .
6 6 6 6 6 6
41s / Lv. 8 (Exp 1 / 8)
5 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
6 6 6 ■ 6 6
42s / Lv. 8 (Exp 2 / 8)
5 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
6 6 ■ . 6 6
43s / Lv. 8 (Exp 3 / 8)
5 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
6 ■ . . 6 6
44s / Lv. 8 (Exp 4 / 8)
5 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
■ . . . 6 6
45s / Lv. 8 (Exp 5 / 8)
5 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . ■ 6
49s / Lv. 8 (Exp 6 / 8)
5 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . ■
50s / Lv. 8 (Exp 7 / 8)
■ . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
60s / Lv. 9 (Exp 0 / 9)따라서 답은 60초입니다.
예제 입력 5
plaintext
6 . 6 . 6 1
. . . . . 2
2 3 4 5 6 6
. . . . . 2
. 2 . . . .
3 ■ 3 . . 1
0s / Lv. 2 (Exp 0 / 2)
6 . 6 . 6 1
. . . . . 2
2 3 4 5 6 6
. . . . . 2
. 2 . . . .
3 . 3 . . ■
6s / Lv. 2 (Exp 1 / 2)
6 . 6 . 6 ■
. . . . . 2
2 3 4 5 6 6
. . . . . 2
. 2 . . . .
3 . 3 . . .
21s / Lv. 3 (Exp 0 / 3)
6 . 6 . 6 .
. . . . . ■
2 3 4 5 6 6
. . . . . 2
. 2 . . . .
3 . 3 . . .
22s / Lv. 3 (Exp 1 / 3)
6 . 6 . 6 .
. . . . . .
■ 3 4 5 6 6
. . . . . 2
. 2 . . . .
3 . 3 . . .
28s / Lv. 3 (Exp 2 / 3)
6 . 6 . 6 .
. . . . . .
. 3 4 5 6 6
. . . . . 2
. ■ . . . .
3 . 3 . . .
31s / Lv. 4 (Exp 0 / 4)
6 . 6 . 6 .
. . . . . .
. ■ 4 5 6 6
. . . . . 2
. . . . . .
3 . 3 . . .
33s / Lv. 4 (Exp 1 / 4)
6 . 6 . 6 .
. . . . . .
. . 4 5 6 6
. . . . . 2
. . . . . .
■ . 3 . . .
37s / Lv. 4 (Exp 2 / 4)
6 . 6 . 6 .
. . . . . .
. . 4 5 6 6
. . . . . 2
. . . . . .
. . ■ . . .
39s / Lv. 4 (Exp 3 / 4)
6 . 6 . 6 .
. . . . . .
. . 4 5 6 6
. . . . . ■
. . . . . .
. . . . . .
44s / Lv. 5 (Exp 0 / 5)
6 . 6 . 6 .
. . . . . .
. . ■ 5 6 6
. . . . . .
. . . . . .
. . . . . .
48s / Lv. 5 (Exp 1 / 5)따라서 답은 48초입니다.
예제 입력 6
cpp
1 1 1 1 1 1
2 2 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
. . . . . 6
. . . . . ■
0s / Lv. 2 (Exp 0 / 2)
1 ■ 1 1 1 1
2 2 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
. . . . . 6
. . . . . .
9s / Lv. 2 (Exp 1 / 2)
■ . 1 1 1 1
2 2 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
. . . . . 6
. . . . . .
10s / Lv. 3 (Exp 0 / 3)
. . 1 1 1 1
■ 2 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
. . . . . 6
. . . . . .
11s / Lv. 3 (Exp 1 / 3)
. . 1 1 1 1
. ■ 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
. . . . . 6
. . . . . .
12s / Lv. 3 (Exp 2 / 3)
. . 1 1 1 1
. . 6 2 2 3
2 ■ 5 2 2 3
2 2 2 4 6 3
. . . . . 6
. . . . . .
13s / Lv. 4 (Exp 0 / 4)
. . 1 1 1 1
. . 6 2 2 3
■ . 5 2 2 3
2 2 2 4 6 3
. . . . . 6
. . . . . .
14s / Lv. 4 (Exp 1 / 4)
. . 1 1 1 1
. . 6 2 2 3
. . 5 2 2 3
■ 2 2 4 6 3
. . . . . 6
. . . . . .
15s / Lv. 4 (Exp 2 / 4)
. . 1 1 1 1
. . 6 2 2 3
. . 5 2 2 3
. ■ 2 4 6 3
. . . . . 6
. . . . . .
16s / Lv. 4 (Exp 3 / 4)
. . 1 1 1 1
. . 6 2 2 3
. . 5 2 2 3
. . ■ 4 6 3
. . . . . 6
. . . . . .
17s / Lv. 5 (Exp 0 / 5)
. . 1 1 1 1
. . 6 2 2 3
. . 5 2 2 3
. . . ■ 6 3
. . . . . 6
. . . . . .
18s / Lv. 5 (Exp 1 / 5)
. . 1 1 1 1
. . 6 2 2 3
. . 5 ■ 2 3
. . . . 6 3
. . . . . 6
. . . . . .
19s / Lv. 5 (Exp 2 / 5)
. . 1 1 1 1
. . 6 ■ 2 3
. . 5 . 2 3
. . . . 6 3
. . . . . 6
. . . . . .
20s / Lv. 5 (Exp 3 / 5)
. . 1 ■ 1 1
. . 6 . 2 3
. . 5 . 2 3
. . . . 6 3
. . . . . 6
. . . . . .
21s / Lv. 5 (Exp 4 / 5)
. . ■ . 1 1
. . 6 . 2 3
. . 5 . 2 3
. . . . 6 3
. . . . . 6
. . . . . .
22s / Lv. 6 (Exp 0 / 6)
. . . . ■ 1
. . 6 . 2 3
. . 5 . 2 3
. . . . 6 3
. . . . . 6
. . . . . .
24s / Lv. 6 (Exp 1 / 6)
. . . . . ■
. . 6 . 2 3
. . 5 . 2 3
. . . . 6 3
. . . . . 6
. . . . . .
25s / Lv. 6 (Exp 2 / 6)
. . . . . .
. . 6 . 2 ■
. . 5 . 2 3
. . . . 6 3
. . . . . 6
. . . . . .
26s / Lv. 6 (Exp 3 / 6)
. . . . . .
. . 6 . ■ .
. . 5 . 2 3
. . . . 6 3
. . . . . 6
. . . . . .
27s / Lv. 6 (Exp 4 / 6)
. . . . . .
. . 6 . . .
. . 5 . ■ 3
. . . . 6 3
. . . . . 6
. . . . . .
28s / Lv. 6 (Exp 5 / 6)
. . . . . .
. . 6 . . .
. . 5 . . ■
. . . . 6 3
. . . . . 6
. . . . . .
29s / Lv. 7 (Exp 0 / 7)
. . . . . .
. . 6 . . .
. . 5 . . .
. . . . 6 ■
. . . . . 6
. . . . . .
30s / Lv. 7 (Exp 1 / 7)
. . . . . .
. . 6 . . .
. . 5 . . .
. . . . ■ .
. . . . . 6
. . . . . .
31s / Lv. 7 (Exp 2 / 7)
. . . . . .
. . 6 . . .
. . 5 . . .
. . . . . .
. . . . . ■
. . . . . .
33s / Lv. 7 (Exp 3 / 7)
. . . . . .
. . 6 . . .
. . ■ . . .
. . . . . .
. . . . . .
. . . . . .
38s / Lv. 7 (Exp 4 / 7)
. . . . . .
. . ■ . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
39s / Lv. 7 (Exp 5 / 7)따라서 답은 39초입니다.