글 읽기 - 정해와는 다른 아이디어이긴 한데 잘못된 부분이 있을까요?

clrmt 4년 전 0

평범하게 푸는건 식상해서 새로운 방법으로 시도하려고 노력을 해봤습니다.

이대로 코드를 구현했더니 18%에서 틀렸다고 나오는데, 아이디어에 잘못된 부분이 있을까요?

우선 이 아이디어는 고인물과 안고인물을 구분해야 합니다.

만약 어떤 한 칸이 녹으면 인접한 8군데의 바다는 연쇄적으로 안고인물이 됩니다.

이제, 어떤 칸이 녹았을 때 섬이 몇 개로 분리되는지를 셀 것입니다.

위에서부터 아래로, 그리고 왼쪽에서부터 오른쪽으로 탐색합니다.(사실 탐색순서는 상관없습니다.)

만약 어떤 칸이 녹으면, 주위 8칸을 시계방향으로 따라가면서 변을 공유하는 섬(I), 꼭짓점을 공유하는 안고인물(s)이 번갈아 등장하는 횟수를 셉니다.

위 그림에서는 S-I 전환수가 3이므로, 3개의 섬으로 나누어집니다.(분리 카운트 +2)

그리고 다음의 섬을 탐색하면, 인접한 4곳이 바다이므로 분리 카운트를 감소시킵니다.

최종적으로 위의 케이스에서는 분리 카운트가 0이 되었으므로 섬이 분리되지 않습니다.

위와 같은 케이스가 있다면 S-I 전환수가 2이므로 2개로 분리됩니다. 한편 섬의 안쪽이 고인물일 경우에는 S-I 전환수가 1이므로 분리되지 않습니다.

이를 1사이클 반복할 때마다,

최종 분리 카운트가 0이면 분리되지 않음, 음수이면 섬이 전부 없어진 것, 양수이면 섬이 분리된 것으로 생각하였습니다.

여기에 잘못된 부분이 있나요?

※반례 찾기를 위해 소스 코드를 올려두겠지만, 코드 오류보다는 아이디어만 검증해 주셨으면 합니다.

// 난잡합니다. 분석은 권장하지 않습니다.
#include <iostream>
using namespace std;

int n, m;
int board[301][301];

const int isolateSea = 32;
const int firstSea = 32;
int turn = 96;

void recurseArea(int y, int x);

void recurse(int y, int x) {

	if (y < 0 || x < 0 || y >= n || x >= m) {
		return;
	}

	if (board[y][x] == firstSea) {
		board[y][x] = turn - 32;
		recurseArea(y, x);
	}

}

void recurseArea(int y, int x) {
	recurse(y - 1, x - 1);
	recurse(y - 1, x + 0);
	recurse(y - 1, x + 1);
	recurse(y + 0, x - 1);
	// recurse(y + 0, x + 0);
	recurse(y + 0, x + 1);
	recurse(y + 1, x - 1);
	recurse(y + 1, x + 0);
	recurse(y + 1, x + 1);
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;

	int i, j;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0) {
				board[i][j] = isolateSea;
			}
		}
	}

	int rQueue[10001]; // not queue
	int rQueueSize = 0;
	int rQueueI;

	for (i = 1; i < n - 1; i++) {
		for (j = 1; j < m - 1; j++) {
			if (board[i][j] > 0) {
				if (board[i][j] <= 10) {
					if (board[i - 1][j] >= firstSea
						|| board[i + 1][j] >= firstSea
						|| board[i][j - 1] >= firstSea
						|| board[i][j + 1] >= firstSea
						) {
						rQueue[rQueueSize++] = i * 1000 + j;
					} else {
						board[i][j] |= 0b10000; // frozen
					}
				}
			}
		}
	}

	recurse(0, 0);

	int y, x;
	int d;
	int dy[4] = {-1, 0, 1, 0};
	int dx[4] = { 0, 1, 0, -1 };



	int splitIsland;

	int a, b;
	int nextA;

	// 32 = isolate sea
	//
	while (rQueueSize > 0) {

		splitIsland = 0;

		turn += 32;

		for (rQueueI = 0; rQueueI < rQueueSize; rQueueI++) {

			y = rQueue[rQueueI] / 1000;
			x = rQueue[rQueueI] % 1000;

			for (d = 0; d < 4; d++) {

				if (32 <= board[y + dy[d]][x + dx[d]] && board[y + dy[d]][x + dx[d]] < turn) {
					// sea
					board[y][x]--;
				}

			}

			if (board[y][x] <= 0) {
				// melt

				if (32 <= board[y - 1][x]
					&& 32 <= board[y + 1][x]
					&& 32 <= board[y][x - 1]
					&& 32 <= board[y][x + 1]
					) {
					splitIsland--;
				} else {

					b = 0;
					if (board[y - 1][x] <= 32) {
						// island or isolate sea
						a = -1;
					} else {
						a = 1;
					}

					if (board[y - 1][x + 1] <= 32) {
						nextA = 0;
					} else {
						nextA = 1;
					}
					if (a * nextA < 0) {
						b++;
						a = -a;
					}

					if (board[y][x + 1] <= 32) {
						nextA = -1;
					} else {
						nextA = 1;
					}
					if (a * nextA < 0) {
						b++;
						a = -a;
					}

					if (board[y + 1][x + 1] <= 32) {
						nextA = 0;
					} else {
						nextA = 1;
					}
					if (a * nextA < 0) {
						b++;
						a = -a;
					}

					if (board[y + 1][x] <= 32) {
						nextA = -1;
					} else {
						nextA = 1;
					}
					if (a * nextA < 0) {
						b++;
						a = -a;
					}

					if (board[y + 1][x - 1] <= 32) {
						nextA = 0;
					} else {
						nextA = 1;
					}
					if (a * nextA < 0) {
						b++;
						a = -a;
					}

					if (board[y][x - 1] <= 32) {
						nextA = -1;
					} else {
						nextA = 1;
					}
					if (a * nextA < 0) {
						b++;
						a = -a;
					}

					if (board[y - 1][x - 1] <= 32) {
						nextA = 0;
					} else {
						nextA = 1;
					}
					if (a * nextA < 0) {
						b++;
						a = -a;
					}

					if (board[y - 1][x] <= 32) {
						nextA = -1;
					} else {
						nextA = 1;
					}
					if (a * nextA < 0) {
						b++;
						a = -a;
					}

					if (b != 0) {
						splitIsland += (b / 2) - 1;
					}

				}

				// convert to sea
				board[y][x] = turn;

				rQueueSize--;
				rQueue[rQueueI] = rQueue[rQueueSize];
				rQueueI--;

				// detect isolate Sea -> transform it to normal sea
				recurseArea(y, x);

				// frozen island -> normal island
				for (d = 0; d < 4; d++) {
					if ((board[y + dy[d]][x + dx[d]] & 0b10000) > 0) {
						board[y + dy[d]][x + dx[d]] &= ~0b10000;
						rQueue[rQueueSize++] = (y + dy[d]) * 1000 + (x + dx[d]);
					}
				}

			}

		}

		if (splitIsland < 0) {
			cout << "0";
			return 0;
		} else if(splitIsland > 0) {
			break;
		}

	}

	cout << (turn / 32) - 3;

}

sait2000 4년 전 2

안 풀어서 잘 모르겠는데 이런 거 들어올 수 있나요?

7
0 0 0 0 0 0
9 9 9 9 9 0
9 0 1 0 9 0
9 0 9 0 9 0
9 0 0 0 9 0
9 9 9 9 9 0
0 0 0 0 0 0

clrmt 4년 전 0

아 이런 케이스가 있군요... 그냥 정해로 가야겠네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

정해와는 다른 아이디어이긴 한데 잘못된 부분이 있을까요?

clrmt 4년 전 0

sait2000 4년 전 2

clrmt 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말