문제
NxN 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다.
한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있다.
처음 아기상어의 크기는 2이고 아기 상어는 1초에 상하좌우로 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고 크기가 작은 물고기만 먹을 수 있다.
아기 상어는 어디로 이동할지 다음과 같은 방법으로 정한다.
- 더 이상 먹을 수 있는 물고기가 없다면 엄마 상어에게 도움 요청한다.
- 먹을 수 있는 물고기가 한 마리면 그 물고기를 먹으러 간다.
- 먹을 수 있는 물고기가 두 마리 이상이라면 거리가 가장 가까운 물고기를 먹는다. => 거리가 가까운 물고기가 2마리 이상이라면 가장 위에 있는 물고기 => 그런 물고기 많다면 가장 왼쪽에 있는 물고기
아기 상어는 물고기가 있는 칸에 도착하자마자 물고기를 먹으며 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다.
아기 상어가 몇 초동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하라
입력
첫째 줄에 공간의 크기 N(2 이상 20 이하)
둘째 줄부터 공간의 상태가 주어진다.
0은 빈칸, 1 2 3 4 5 6은 물고기의 크기
9는 아기상어의 위치
출력
엄마상어에게 도움을 요청하기 전까지의 시간을 출력
접근
가장 먼저 상어를 어떻게 이동시키는지 생각해봤다.
상어는 가까운 물고기부터 먹기 때문에 BFS를 활용하여 물고기를 찾아다니도록 하였다. 이때 이동하는 주체는 상어가 되기 때문에 상어에 대한 구조체를 만들었다. 이 구조체는 BFS에서 큐에 사용된다.
이제 물고기를 선택하는 기준대로 물고기를 찾아야한다.
가까운 물고기가 여러 개라면 Y가 낮고, Y도 같다면 X가 낮은 물고기를 찾아야 한다. BFS는 가까운 물고기부터 탐색하기 때문에 이미 먹을 물고기가 담겨있는데 더 멀리 있는 물고기가 다음 큐에서 나온다면 종료를 시켜야 한다.
엄마의 도움은 언제 요청할까?
BFS 탐색을 진행했는데 먹을 물고기가 없다면 엄마의 도움을 요청해야 한다. 따라서 물고기를 먹었다면 어떻게든 표시를 해주어야 한다.
구현
상어는 먹을 물고기를 찾을 때 BFS로 탐색을 한다. 따라서 SHARK에 대한 구조체를 선언하여 상어의 위치와 거리(시간)를 포함시켰다.
struct SHARK {
int y, x;
int time;
};
맵에 대한 정보를 입력받을 때 9는 상어를 의미하고 9가 나왔을 때 상어에 대한 정보를 초기화시켜주고 해당 위치를 다시 0으로 변경한다. 실질적으로 9가 맵에서 움직이는 것이 아니다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
if (map[i][j] == 9) {
shark.y = i;
shark.x = j;
shark.time = 0;
shark_size = 2;
map[i][j] = 0;
}
}
}
그다음 while문을 통해 엄마에게 도움을 요청하기 전까지 계속해서 물고기를 탐색할 것이다. 따라서 is_update라는 변수를 통해 먹은 물고기가 있다면 true로 바꿔주도록 한다. 이 while문은 is_update가 false일 때 종료된다(먹을 물고기가 없을 때).
bool is_update = true;
while (is_update) {
// 엄마 도움 요청 전까지 물고기 탐색하기
}
queue를 선언하여 상어가 움직이면서 먹을 물고기를 찾는다. 이때 방문한 곳은 또 방문하지 않도록 해야 무한루프에 빠지지 않는다. 따라서 visited이라는 2차원 배열을 선언하고 상어가 있는 곳은 true로 해준다.
while (is_update) {
is_update = false;
bool visited[20][20] = { false, };
visited[shark.y][shark.x] = true;
queue<SHARK> q;
q.push(shark);
}
이후 먹을 물고기의 후보를 정하기 위해 feed라는 SHARK 구조체를 선언한다. feed.y를 20으로 준이유는 BFS는 거리가 작은 물고기부터 찾기 때문에 Y와 X만 비교하도록 하였고 처음 물고기를 feed에 넣기 위해 feed.y를 큰 값으로 선언한 것이다. 또한 feed.time의 -1은 현재 먹을 물고기를 찾지 못했다는 의미이다.
SHARK feed;
feed.y = 20;
feed.time = -1;
이제 BFS를 통해 먹을 물고기를 찾아보자. 기본적인 구조는 비슷하며 feed.time이 -1이 아닌데(이미 먹을 물고기를 찾음) 다음 나오는 상어의 위치가 더 멀다면 더 이상 탐색하는 의미가 없기 때문에 종료시킨다.
그리고 0이 아닌 작은 물고기를 찾았다면 is_update를 true로 변경해주고 y와 x를 비교하여 feed를 업데이트해준다.
이후 상하좌우를 탐색하여 상어가 다음에 이동할 장소를 선택한다. 이때 주의할 것은 visieted가 false인 곳에 방문하고 방문했다면 true로 변경해주어야 한다.
while (!q.empty()) {
SHARK cur = q.front();
q.pop();
if (feed.time != -1 && cur.time > feed.time)
break;
if (map[cur.y][cur.x] < shark_size&&map[cur.y][cur.x] != 0) {
is_update = true;
if (cur.y < feed.y || (cur.y == feed.y&&cur.x < feed.x))
feed = cur;
}
for (int d = 0; d < 4; d++) {
SHARK next;
next.y = cur.y + dir[d][0];
next.x = cur.x + dir[d][1];
next.time = cur.time + 1;
if (map[next.y][next.x] <= shark_size && RangeCheck(next.y, next.x)&&visited[next.y][next.x]==false) {
visited[next.y][next.x] = true;
q.push(next);
}
}
}
먹을 물고기를 찾았다면 진행해야 될 것이 있다. 상어가 먹은 물고기의 수를 증가시키고 먹은 곳은 0으로 변경하며 먹은 물고기와 상어의 크기가 같다면 상어의 크기를 증가시키도록 한다. 이후 is_update가 false가 되면 최종적으로 shark.time을 출력하도록 한다.
if (is_update) {
++shark_eat;
shark = feed;
map[shark.y][shark.x] = 0;
if (shark_size == shark_eat) {
++shark_size;
shark_eat = 0;
}
}전체 코드
#include "pch.h"
#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>
using namespace std;
struct SHARK {
int y, x;
int time;
};
const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
int N;
int map[20][20];
int shark_size, shark_eat;
bool RangeCheck(int y, int x) {
return (y >= 0 && y < N) && (x >= 0 && x < N);
}
int main()
{
cin >> N;
SHARK shark;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
if (map[i][j] == 9) {
shark.y = i;
shark.x = j;
shark.time = 0;
shark_size = 2;
map[i][j] = 0;
}
}
}
bool is_update = true;
while (is_update) {
is_update = false;
bool visited[20][20] = { false, };
visited[shark.y][shark.x] = true;
queue<SHARK> q;
q.push(shark);
// 먹을 물고기를 저장함
SHARK feed;
feed.y = 20; // y비교를 위해
feed.time = -1;
while (!q.empty()) {
SHARK cur = q.front();
q.pop();
if (feed.time != -1 && cur.time > feed.time)
break;
if (map[cur.y][cur.x] < shark_size&&map[cur.y][cur.x] != 0) {
is_update = true;
if (cur.y < feed.y || (cur.y == feed.y&&cur.x < feed.x))
feed = cur;
}
for (int d = 0; d < 4; d++) {
SHARK next;
next.y = cur.y + dir[d][0];
next.x = cur.x + dir[d][1];
next.time = cur.time + 1;
if (map[next.y][next.x] <= shark_size && RangeCheck(next.y, next.x)&&visited[next.y][next.x]==false) {
visited[next.y][next.x] = true;
q.push(next);
}
}
}
if (is_update) {
++shark_eat;
shark = feed;
map[shark.y][shark.x] = 0;
if (shark_size == shark_eat) {
++shark_size;
shark_eat = 0;
}
}
}
cout << shark.time << endl;
return 0;
}
느낀점
가장 먼저 정해줘야 할것은 상어의 이동이 언제 멈출 것인지 정하는 것이다. 다른 것을 먼저 정하면 모든 코드가 뒤죽박죽이 되었다. 따라서 while문으로 탐색을 한다면 탈출조건을 먼저 정하고 다음 동작을 구현한다.
'알고리즘 풀이 > 백준' 카테고리의 다른 글
| [백준 2667] 단지번호붙이기 cpp (0) | 2021.02.10 |
|---|---|
| [백준 1012] 유기농 배추 cpp (0) | 2021.02.10 |
| [백준 15686] 치킨 배달 (0) | 2021.02.07 |
| [백준 14503] 로봇 청소기 cpp (0) | 2021.02.06 |
| [백준 1946] 신입 사원 cpp (0) | 2021.02.05 |