[백준/C++] 16236 - 아기 상어

풀이 시간: 1h42m11s75(초반 삽질) + 3h05m13s35

시간 복잡도: O(N^2 * log N) // log N은 우선순위 큐의 삽입 및 삭제 연산의 시간 복잡도

공간 복잡도: O(N^2)

문제

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초에 상하좌우로 인접한 한 칸씩 이동한다"고 했는데,

왜 갑자기 설명 중간에 거리가 가장 가까운 물고기를 먹으러 가라고 하는걸까?

인접한 상하좌우 한 칸씩은 모두 같은 거리일텐데..?

 

만약 상하좌우로 검사를 했을 때 한 칸 이상 멀리 떨어진 거리에 가장 가까운 물고기가 있다고 하면, "한 칸씩 이동할 때 1초 걸린다"고 설명 윗쪽에 분명히 쓰여있었는데, 갑자기 설명 아랫 부분에서는 "아기 상어의 이동이 1초 걸린다"고 써있다.

도대체 그럼 한 칸 이상 걸리는 거리는 1초인가 N초인가.... 

 

그리고 인접한 상하좌우 4방향을 모두 탐색을 했을 때 만약 물고기가 하나도 없으면, 어디 방향부터 다시 탐색을 해야하는거지..? 그냥 큐에 넣는 순서대로 하는게 맞을까? 일단 가까운 거리의 물고기가 도달할 때까지 끝까지 가봐야하나?

 

거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

 

"그러한 물고기가 여러마리라면" 이건 대체 무슨 뜻이지? 거리가 가까운 물고기가 많은 것과 여러마리인 것은 다른 의미였던 것인가?

거리가 "가장" 가까운 물고기가 많다면 그 중 가장 위에 있는 물고기를 먹고, 그러한 물고기가 여러마리라면 가장 왼쪽에 있는 물고기를 먹어라..??? 뭐지.. 그러한이 대체 무슨 뜻일까.

상어를 기준으로 가장 위에 있는 물고기는 북쪽의 물고기이다. 근데 그런 물고기가 여러마리라니.. 뭐지?

 

일단 질문게시판을 찾으면서 문제 조건에 대해서 질문한 글들을 찾아보며 문제 조건을 명확히 이해해보려고 했다.

 

아래 아기 상어 문제의 질문 게시판에 각 예제의 시뮬레이션을 모두 보여준 글이 있어서 아래 글을 참고하여 다시 문제를 분석해봤다.

https://www.acmicpc.net/board/view/100687

글 읽기 - 【아기 상어】 예제 시뮬레이션

---

위 시뮬레이션을 하나씩 계산해보며 본 문제를 분석해보니, 큐를 사용하여 풀어야할 것 같아서 큐에다가 현재 아기 상어의 위치와 이동 거리를 저장해주었다.

즉, 인접한 상하좌우 칸을 탐색하면서 물고기가 없는 칸이라도 일단 큐에 좌표를 삽입하고 각 큐마다 이동 거리를 중첩시켜 더해주는 것이다.

 

이때 이동 거리는 먹을 수 있는 물고기를 발견했을 때 현재 아기 상어의 위치에서 해당 물고기를 발견한 곳까지의 거리를 측정하여 상어의 이동 시간을 추가해주기 위해 필요하다.

 

본 문제의 핵심은 상하좌우로 물고기가 있는 위치를 탐색하며 현재 위치에서 가장 가까운 물고기를 찾아 먹는 것이다.

 

여기서 중요한 것은 물고기와 상어의 크기이다.

1. 만약 특정 방향으로 진행하는 도중 어떤 물고기를 만났을 때, 해당 물고기의 크기가 상어의 크기보다 큰 경우에는 지나갈 수 없으므로 해당 방향은 더 이상 측정이 불가능하다. 따라서 해당 방향에서의 다음 위치는 큐에 넣지 않는다.
2. 만약 해당 물고기의 크기가 상어의 크기와 같다면, 먹을 수는 없지만 지나갈 수는 있다. 따라서 빈칸과 똑같은 방식으로 진행하면 된다. 즉, 다음 위치를 탐색하기 위해 해당 물고기가 있는 위치를 큐에 넣으면 된다.
3. 만약 해당 물고기의 크기가 상어의 크기보다 작다면, 먹을 수 있는 물고기이므로 먹는다.

물고기를 먹을 때 주의해야할 점은 가장 가까운 물고기가 여러 마리일 경우를 확인해야 한다.

참고로 나는 이 부분을 제대로 이해 못해서 헤맸었다. 난 무슨 북쪽 물고기부터 북서남동 순서대로 먹으라는 줄 알았다..ㅋ

1. 거리가 가장 가까운 물고기가 여러 마리일 경우, 좌표를 기준으로 y값이 가장 작은 물고기를 선택한다. (좌표 상으로 가장 맨 위에 있는 물고기)
2. 만약, y값이 가장 작은 물고기가 여러 마리일 경우에는, 이들 중 x값이 가장 작은 물고기를 선택하면 된다. 좌표 한 칸에는 한 마리의 물고기만 존재하므로 이렇게 하면 겹칠 일은 없다. (좌표 상으로 가장 왼쪽에 있는 물고기)

나는 위 과정을 구현하기 위해 구조체와 연산자 오버로딩, 그리고 우선순위 큐를 사용해서 구현하였다.

 

이제 물고기를 먹으면 해당 좌표의 값은 빈 칸 즉, 0으로 바뀌고 상어의 위치는 해당 좌표로 갱신되며, 상어가 총 이동한 시간과 먹은 물고기의 수, 상어의 크기가 모두 갱신된다.

 

아기 상어는 맨처음에는 자기 자신의 크기가 2로 측정이 되어있는데, 지금까지 총 먹은 물고기의 개수를 따로 저장하여 그 값과 상어의 크기를 비교하여 두 값이 같을 때만 상어의 크기에 +1을 해주면 된다.

 

갱신된 상어 위치에서 다시 큐를 돌려 상어의 크기보다 작은 먹을 수 있는 물고기가 더 이상 없을 때까지 물고기를 탐색해주면 된다.

 

+ 문제 오류 해결

다르게 푼 건 없다고 생각해서 맞는 답인 줄 알았는데, 자꾸 답이 다르게 나와서 다시 위에 시뮬레이션 글을 차근차근 살펴보며 내 코드에서 이상한 건 없는지 찾아봤다.

 

아니 근데 웬걸 상어 크기가 증가되면 다시 먹은 물고기 개수를 초기화 해주어야 했던 것이다.(;;)

진짜 말도 안된다. 난 당연히 먹은 물고기 수가 누적되는 줄 알았고, 누적된 만큼 한 번 먹을 때마다 계속 커지는 줄 알았다. 근데 그냥 한 번 상어의 크기만큼 물고기를 먹으면 다시 리셋하고 처음부터 개수를 세는 것이었다.. 이것 때문에 시간 엄청 썼다... 그래도 찾아서 다행이다. ㅎ

전체 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
pair<int, int> pos; // 아기 상어의 위치
int N, sharkSize = 2, fishNum = 0, cnt = 0; // 공간 크기, 아기 상어 크기, 먹은 물고기 수, 시간 초
int arr[21][21] = { 0, }, visited[21][21] = { false, };
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
// dir[i][j] : i번째 줄, j번째 칸, 북서남동

struct Shark {
	int i, j, move; // 현재 아기 상어 좌표(i, j), 이동거리: 초깃값 0
	Shark(int _i, int _j, int _move) : i(_i), j(_j), move(_move) {} // 생성자 정의

	bool operator<(const Shark& other) const {
		// i, j, move 모두 더 작은 값을 우선으로 정렬, 이때 move, i, j 순서대로 우선순위 적용
		if (move != other.move) return move > other.move;
		if (i != other.i) return i > other.i;
		return j > other.j;
	}
};

bool babyShark() {
	priority_queue<Shark> pq;
	pq.push({pos.first, pos.second, 0});
	visited[pos.first][pos.second] = true;

	while (!pq.empty()) {
		int cX = pq.top().i;
		int cY = pq.top().j;
		int cM = pq.top().move;
		pq.pop(); // 가장 거리가 가까우면서 가장 맨 위쪽에서 가장 왼쪽에 있는 물고기 꺼냄

		// 물고기 크기가 아기 상어 크기보다 작으면 먹음
		if (arr[cX][cY] != 0 && sharkSize > arr[cX][cY]) {
			arr[cX][cY] = 0; // 현재 위치를 빈칸으로 변경 (물고기를 먹는다는 의미!)
			cnt += cM; // 아기 상어의 총 이동 거리 갱신
			pos = make_pair(cX, cY); // 현재 좌표로 아기 상어 위치 갱신
			fishNum++; // 먹은 물고기 개수 갱신
			if (fishNum == sharkSize) {
				fishNum = 0; // 먹은 물고기 개수 초기화 **** 중요!! ****
				sharkSize++; // 상어 크기 갱신
			}
			memset(visited, false, sizeof(visited)); // 방문 위치 매번 초기화
			return true;
		}

		for (int i = 0; i < 4; ++i) { // 상하좌우로 다음 좌표 탐색
			int nX = cX + dir[i][0], nY = cY + dir[i][1];
			
			// 공간 크기 범위 초과 또는 방문한 위치일 경우 continue
			if (nX < 0 || nX >= N || nY < 0 || nY >= N || visited[nX][nY]) continue;
			if (arr[nX][nY] > sharkSize) continue;

			pq.push({nX, nY, cM + 1});
			visited[nX][nY] = true; // 방문 처리
		}
	}
	return false; // 먹을 물고기가 없는 경우
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) { // 아기 상어 위치 저장
				pos = make_pair(i, j);
				arr[pos.first][pos.second] = 0; 
				// 아기 상어가 현재 있는 위치를 빈칸으로 설정 (검사 시 헷갈리지 않도록)
				// 따로 상어 좌표를 저장해놨으므로, 물고기를 먹은 위치만 pos값에 갱신해줌
			}
		}
	}
	while(babyShark());
	cout << cnt;
	return 0;
}

 

https://www.acmicpc.net/problem/16236

16236번: 아기 상어