아기 상어 (Gold 4)
문제
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
접근법
이번 문제는 BFS를 활용하여 풀 수 있습니다. 그리고 구현할 것이 상당히 많은 문제입니다. 그리고 먹이를 한번 먹을 때마다 BFS 탐색을 진행하기 때문에 탐색량도 많은 문제입니다. 하지만 정상적으로 구현하였다면 C++ 기준으로 0ms가 나오기 때문에 시간 초과가 발생하였다면 로직의 문제로 무한 루프가 형성되었을 가능성이 큽니다. 쉽게 놓칠 수 있는 부분이 문제에서 상어의 위치를 9로 주어졌는데, 먹이를 먹고 상어의 위치를 9로 마크한다면 문제가 생길 수 있습니다. 왜냐하면 상어가 먹이를 계속 먹어 크기가 10 이상이 된다면 현재 상어의 위치를 먹이로 인식하기 때문입니다. 따라서 상어의 위치를 입력받을 때 9를 받지만 배열에 저장할 때는 0 혹은 충분히 큰 값을 사용해야 합니다.
- 더 이상 먹을 수 있는 먹이가 없을 때까지 아래를 반복합니다.
- 먹이를 탐색합니다.
- 탐색한 위치의 먹이를 먹습니다.
먹이를 탐색하기 위한 BFS는 현재 상어의 위치에서 탐색을 시작하여 가장 가까운 위치의 먹이를 탐색합니다. 여기서 까다로운 점은 거리가 같은 경우 가장 위쪽, 높이가 같은경우 가장 왼쪽 먹이를 선택해야 한다는 점입니다. 이를 위해서 우선순위 큐를 사용하면 간결하게 작성할 수 있지만 우선순위 큐를 사용하게 되면 시간 복잡도가 \(log(n)\)만큼 커지기 때문에 우선순위 큐를 사용하지 않았습니다. 대신 동일한 거리의 먹이들 중 가장 왼쪽 위의 먹이를 탐색하는 과정을 추가하였습니다. (물론 우선순위큐를 사용하여 시간 복잡도가 \(log(n)\) 만큼 커지더라도 충분히 시간 내에 계산을 끝낼 수 있습니다.)
구현
위의 의사 코드를 main함수에 구현하면 다음과 같습니다.
int main()
{
Shark baby{};
baby.size = 2;
InputData(N, baby.pos);
int answer{};
Pos target{};
int dist{};
while (BFS(N, baby, target, dist)) // 먹이를 탐색, 먹이가 존재할 경우 true
{
baby.Eat(target); // 탐색한 먹이를 먹음
answer += dist;
}
}Shark 클래스
Shark는 상어가 먹이를 먹는 과정을 Eat 함수로 추상화하여 관리하는 것이 편하기 때문에 클래스로 다음과 같이 구현할 수 있습니다.
// pos: {0,0} / size 2 / feeds 0으로 초기화
class Shark {
private:
Pos pos{};
int size{2};
int feeds{};
public:
Shark() {}
Pos GetPos() { return pos; }
int GetSize() { return size; }
void SetPos(Pos _pos) { pos = _pos; }
void Eat(Map& map, Pos feedPos)
{
Node* feed = Node::GetNode(map, feedPos);
feed->size = 0; // 먹이 노드 빈칸으로 설정
pos.y = feedPos.y; // 상어 위치 이동
pos.x = feedPos.x;
feeds++;
if (feeds == size)
{
feeds = 0;
size++;
}
}
};BFS
BFS함수에서는 target과 dist를 아래와 같이 L-value로 받아서 탐색 결과 먹이의 위치와 먹이까지의 거리를 전달해줍니다. BFS를 여러 번 호출해야 하기 때문에 호출 시마다 방문 기록을 초기화해야합니다. 방문기록을 초기화하기 위한 과정은 Init 함수로 추상화하였습니다. 그리고 먹이를 발견한 경우 같은 거리의 먹이들 사이에서 가장 위쪽, 왼쪽의 먹이로 갱신합니다. 이후 BFS 탐색은 일반적인 BFS 탐색과정과 동일합니다.
bool BFS(Map& map, int N, Shark& baby, Pos& target, int& dist)
{
// 방문 기록 초기화
Init(map);
// 먹이 기록 초기화
dist = INF;
target.y = INF;
target.x = INF;
Node* start = Node::GetNode(map, baby.GetPos());
start->dist = 0;
queue<Node*> q;
q.push(start);
while (!q.empty())
{
Node* cur = q.front();
q.pop();
// 먹이 발견
if (0 < cur->size && cur->size < baby.GetSize() && dist >= cur->dist)
{
dist = cur->dist;
// 새로 발견한 먹이의 y위치가 같다면
if (target.y == cur->pos.y)
{
// 더 왼쪽에 있는 값 사용
if (target.x > cur->pos.x)
{
target.y = cur->pos.y;
target.x = cur->pos.x;
}
}
else
{
// 새로 발견한 먹이 y위치가 다르면
if (target.y > cur->pos.y)
{
// 더 위에 있는 값 사용
target.y = cur->pos.y;
target.x = cur->pos.x;
}
}
}
if (target.y < INF && dist < cur->dist)
{
//먹이를 발견했다면 탐색 종료
break;
}
for (int i = 0; i < 4; ++i)
{
Pos nextPos;
nextPos.y = cur->pos.y + dy[i];
nextPos.x = cur->pos.x + dx[i];
Node* next = Node::GetNode(map, nextPos);
if (next->dist == INF && next->size <= baby.GetSize())
{
next->dist = cur->dist + 1;
q.push(next);
}
}
}
if (dist < INF) // 먹이를 발견한 경우
return true;
else // 먹이 없음
return false;
}전체 구현
아래의 코드와 같이 전체 프로그램을 구현할 수 있습니다.
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define endl '\n'
using namespace std;
const int INF = 1'000;
// 동일한 거리에 먹이가 있을 경우 위쪽 먼저 탐색, y가 동일할경우 왼쪽 우선 탐색
const int dy[4] = { -1, 0, 0, 1 };
const int dx[4] = { 0, -1, 1, 0 };
using Map = vector<vector<struct Node>>;
struct Pos {
int y{};
int x{};
};
struct Node {
Pos pos{};
int size{};
int dist{ INF };
static Node* GetNode(Map& map, Pos pos)
{
return &map[pos.y][pos.x];
}
};
// pos: {0,0} / size 2 / feeds 0으로 초기화
class Shark {
private:
Pos pos{};
int size{2};
int feeds{};
public:
Shark() {}
Pos GetPos() { return pos; }
int GetSize() { return size; }
void SetPos(Pos _pos) { pos = _pos; }
void Eat(Map& map, Pos feedPos)
{
Node* feed = Node::GetNode(map, feedPos);
feed->size = 0; // 먹이 노드 빈칸으로 설정
pos.y = feedPos.y; // 상어 위치 이동
pos.x = feedPos.x;
feeds++;
if (feeds == size)
{
feeds = 0;
size++;
}
}
};
void InputData(Map& map, int N, Shark& baby)
{
for (int i = 0; i < N + 2; ++i)
{
map[i].resize(N + 2);
for (int j = 0; j < N + 2; ++j)
{
map[i][j].pos.y = i;
map[i][j].pos.x = j;
map[i][j].size = INF; // 여백 공간은 큰 값을 가짐
}
}
for (int i = 1; i < N + 1; ++i)
{
for (int j = 1; j < N + 1; ++j)
{
scanf("%d ", &map[i][j].size);
if (map[i][j].size == 9)
{
// 상어일 경우 상어 위치만 받아 오고 size는 0으로 설정
map[i][j].size = 0;
Pos start{};
start.y = i;
start.x = j;
baby.SetPos(start);
}
}
}
}
void Init(Map& map)
{
for (auto& row : map)
{
for (auto& node : row)
{
node.dist = INF;
}
}
}
bool BFS(Map& map, int N, Shark& baby, Pos& target, int& dist)
{
// 방문 기록 초기화
Init(map);
// 먹이 기록 초기화
dist = INF;
target.y = INF;
target.x = INF;
Node* start = Node::GetNode(map, baby.GetPos());
start->dist = 0;
queue<Node*> q;
q.push(start);
while (!q.empty())
{
Node* cur = q.front();
q.pop();
// 먹이 발견
if (0 < cur->size && cur->size < baby.GetSize() && dist >= cur->dist)
{
dist = cur->dist;
// 새로 발견한 먹이의 y위치가 같다면
if (target.y == cur->pos.y)
{
// 더 왼쪽에 있는 값 사용
if (target.x > cur->pos.x)
{
target.y = cur->pos.y;
target.x = cur->pos.x;
}
}
else
{
// 새로 발견한 먹이 y위치가 다르면
if (target.y > cur->pos.y)
{
// 더 위에 있는 값 사용
target.y = cur->pos.y;
target.x = cur->pos.x;
}
}
}
if (target.y < INF && dist < cur->dist)
{
//먹이를 발견했다면 탐색 종료
break;
}
for (int i = 0; i < 4; ++i)
{
Pos nextPos;
nextPos.y = cur->pos.y + dy[i];
nextPos.x = cur->pos.x + dx[i];
Node* next = Node::GetNode(map, nextPos);
if (next->dist == INF && next->size <= baby.GetSize())
{
next->dist = cur->dist + 1;
q.push(next);
}
}
}
if (dist < INF) // 먹이를 발견한 경우
return true;
else // 먹이 없음
return false;
}
int main() {
int N; // N(2 ≤ N ≤ 20)
scanf("%d ", &N);
Map map(N + 2);
Shark baby{};
InputData(map, N, baby);
int answer{};
Pos target{};
int dist{};
while (BFS(map, N, baby, target, dist))
{
baby.Eat(map, target);
answer += dist;
}
printf("%d\n", answer);
return 0;
}