글 읽기 - 왜 틀렸을까요? ㅠ 반례가 있을까요?

kim031504 3년 전 0

다음의 절차를 통해 문제 해결을 하고자 하였습니다.

1. 각 빙산을 인접한 바닷물의 면 만큼 녹여준다.

2. 빙산이 다 녹아 더 분리할 수 없는지 확인한다.

3. 아직 빙산이 다 녹지 않았다면 일단 현재 빙산 상태를 BFS 탐색하여 2개 이상으로 분리되어 있는지 확인한다.

4. 2개 이상으로 분리되어 있다면 while문을 탈출한다.

일단 예제 테스트 케이스나 질문에 나와있는 여러 테스트 케이스는 통과하는데,

제출하면 틀렸다고 합니다.

혹시 제가 놓치고 있는 부분이 있을까요...?

코드의 자세한 설명은 주석으로 달아놨습니다!

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int MAX = 300;
const int dr[] = { 0, 0, 1, -1 };
const int dc[] = { 1, -1, 0, 0 };

int map[MAX][MAX];
bool check[MAX][MAX];
int N, M;

// 범위 내에 있는가?
bool isInside(int r, int c) {
	if (0 <= r && r < N && 0 <= c && c < M)
		return true;

	return false;
}

// 인접한 바닷물의 면 만큼 녹여준다.
void melt() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (map[r][c] != 0) {
				int zero_cnt = 0;

				for (int k = 0; k < 4; k++) {
					int nr = r + dr[k];
					int nc = c + dc[k];

					if (!isInside(nr, nc)) continue;
					if (map[nr][nc] != 0) continue;

					zero_cnt++;
				}

				map[r][c] -= zero_cnt;

				if (map[r][c] <= 0)
					map[r][c] = 0;
			}
		}
	}
}

// 빙산이 다 녹았는가?
bool isMelted() {
	for (int r = 0; r < N; r++)
		for (int c = 0; c < M; c++)
			if (map[r][c] != 0)
				return false;

	return true;
}

void bfs(int r, int c) {
	queue<pair<int, int>> q;
	q.push(make_pair(r, c));
	check[r][c] = true;

	while (!q.empty()) {
		r = q.front().first;
		c = q.front().second;

		q.pop();

		for (int k = 0; k < 4; k++) {
			int nr = r + dr[k];
			int nc = c + dc[k];

			if (!isInside(nr, nc)) continue;
			if (map[nr][nc] == 0) continue;
			if (check[nr][nc]) continue;
			
			check[nr][nc] = true;
			q.push(make_pair(nr, nc));
		}
	}
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;

	for (int r = 0; r < N; r++)
		for (int c = 0; c < M; c++)
			cin >> map[r][c];

	int year = 0;

	while (true) {
		year++;
		melt();
		memset(check, false, sizeof(check));
		
		// 바닷물이 다 녹아서 분리될 수 없는 경우
		if (isMelted()) {
			year = 0;
			break;
		}

		int cnt = 0;

		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				if (map[r][c] != 0 && !check[r][c]) {
					cnt++;
					bfs(r, c);
				}
			}
		}

		if (cnt >= 2)
			break;
	}

	cout << year << '\n';

	return 0;
}

yj9404 3년 전 1

반례 드립니다.

5 5
0 0 0 0 0
0 0 10 10 0
0 10 0 10 0
0 0 10 10 0
0 0 0 0 0

정답 : 0

출력 : 1

kim031504 3년 전 0

앗!

반례 찾아주셔서 감사합니다!

애초에 처음부터 두 덩이 이상으로 분리된 경우에는 0을 출력해야 하네요.

그래서 다음과 같이 코드 수정을 하였는데, 그래도 자꾸 틀렸다고 합니다 ㅠㅠ

도대체 놓치고 있는 부분이 뭔지 못 찾겠네요...

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int MAX = 300;
const int dr[] = { 0, 0, 1, -1 };
const int dc[] = { 1, -1, 0, 0 };

int map[MAX][MAX];
bool check[MAX][MAX];
int N, M;

// 범위 내에 있는가?
bool isInside(int r, int c) {
	if (0 <= r && r < N && 0 <= c && c < M)
		return true;

	return false;
}

// 인접한 바닷물의 면 만큼 녹여준다.
void melt() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (map[r][c] != 0) {
				int zero_cnt = 0;

				for (int k = 0; k < 4; k++) {
					int nr = r + dr[k];
					int nc = c + dc[k];

					if (!isInside(nr, nc)) continue;
					if (map[nr][nc] != 0) continue;

					zero_cnt++;
				}

				map[r][c] -= zero_cnt;

				if (map[r][c] <= 0)
					map[r][c] = 0;
			}
		}
	}
}

// 바닷물이 다 녹았는가?
bool isMelted() {
	for (int r = 0; r < N; r++)
		for (int c = 0; c < M; c++)
			if (map[r][c] != 0)
				return false;

	return true;
}

void bfs(int r, int c) {
	queue<pair<int, int>> q;
	q.push(make_pair(r, c));
	check[r][c] = true;

	while (!q.empty()) {
		r = q.front().first;
		c = q.front().second;

		q.pop();

		for (int k = 0; k < 4; k++) {
			int nr = r + dr[k];
			int nc = c + dc[k];

			if (!isInside(nr, nc)) continue;
			if (map[nr][nc] == 0) continue;
			if (check[nr][nc]) continue;

			check[nr][nc] = true;
			q.push(make_pair(nr, nc));
		}
	}
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;

	for (int r = 0; r < N; r++)
		for (int c = 0; c < M; c++)
			cin >> map[r][c];

	// 애초에 처음부터 다 녹아있는 경우
	if (isMelted()) {
		cout << 0 << '\n';
		return 0;
	}

	int year = 0;

	while (true) {
		memset(check, false, sizeof(check));

		int cnt = 0;

		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				if (map[r][c] != 0 && !check[r][c]) {
					cnt++;
					bfs(r, c);
				}
			}
		}

		if (cnt >= 2)
			break;

		year++;
		melt();

		if (isMelted()) {
			year = 0;
			break;
		}
	}

	cout << year << '\n';

	return 0;
}

yj9404 3년 전 2

반례가 딱 떠오르진 않는데 모든 빙하가 한꺼번에 녹아야 하는데 melt 함수를 보면 왼쪽 위부터 순서대로 녹네요. 그러면

0 0 0 ...

0 3 5 ...

0 0 0 ...

인 경우에

0 0 0 ...

0 0 3 ...

0 0 0 ...

이 되어야 하는데

0 0 0 ...

0 0 2 ...

0 0 0 ...

이 되어서 틀리는 경우가 생길것 같네요.

kim031504 3년 전 0

와!

여기서 논리적 오류가 있었군요!

난잡하게 작성한 코드인데 구멍난 부분 찾아주셔서 감사합니다!!!

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

문제

문제

출처

ICPC

왜 틀렸을까요? ㅠ 반례가 있을까요?

kim031504 3년 전 0

yj9404 3년 전 1

kim031504 3년 전 0

yj9404 3년 전 2

kim031504 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말