글 읽기 - 제가 해본 테스트케이스로는 어떤게 틀렸는지 못찾겠습니다. ㅜ

woon1113 6년 전 0

틀린 테스트 케이스를 못찾겠어서 어디가잘못됬는지 모르겠네요 ㅜ

첨부터 다시해야하나..

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
int rx, ry, lx, ly, M, N, K, cnt;
int xmin, ymin;
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,1,-1 };
int arr[500];
vector<vector<int> > map(100, vector<int>(100, -1));

void BFS(int x, int y)
{
	queue<pair<int, int> > q;
	q.push(make_pair(x, y));

	if (x == 0 || y == 0) {
		map[x][y] = 1;
	}

	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx<0 || ny<0 || nx>M - 1 || ny>N - 1)
				continue;
			if (map[nx][ny] == 0) {
				q.push(make_pair(nx, ny));
				map[nx][ny] = map[x][y] + 1;
				arr[cnt]++;
			}
		}
	}
}

int main()
{
	cin >> M >> N >> K;

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			map[i][j] += 1;
		}
	}
	for (int i = 0; i < K; i++) {
		cin >> lx >> ly >> rx >> ry;
		ymin = (ry - 1) - ly;
		xmin = (rx - 1) - lx;
		for (int k = 0; k <= ymin; k++) {
			for (int l = 0; l <= xmin; l++) {
				map[ly + k][lx + l] += 1;
			}
		}
	}
	for (int i = 0; i <M; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0) {
				BFS(i, j);
				cnt++;
			}
		}
	}
	sort(arr, arr + cnt);
	cout << cnt << endl;
	for (int i = 0; i < cnt; i++) {
		cout << arr[i]+1  << " ";
	}
}

djm03178 6년 전 1

원인을 한 번 분석해봅시다.

지금 출력을 arr[i]+1로 하고 계신데, 즉 그 말은 arr에 세어진 칸의 개수는 항상 실제 칸보다 1 모자라다는 가정을 하신 거겠죠?

왜 그러냐면 BFS를 처음 시작하는 칸을 세지 않았기 때문입니다.

그리고 시작한 칸을 중복 방문하지 않기 위해서 if (x == 0 || y == 0) { map[x][y] = 1; } 라는 문장을 넣으셨는데, 이 조건이 좀 이상하죠. 왜 x가 0이거나 y가 일 때만 이 처리를 해야 할까요?

간단한 반례로,

3 3 2

0 0 3 1

0 0 1 3

이 경우 남는 칸은 4칸인데, 출력해보면 5칸으로 뜨죠. 그 이유는 BFS가 처음 호출되는 점의 좌표가 y도 x도 0이 아니기 때문에, 다른 칸을 방문했다가 그 칸이 다시 원래의 칸을 또 방문하기 때문에 모든 칸에 대해 arr[cnt]가 증가하기 때문입니다.

woon1113 6년 전 0

와.. 정말 감사합니다 ㅜ

말씀 하신것처럼 출력을 +1을 해줄필요가 없는 거였네요 BFS함수의 처음 if문을 삭제하고

빈블럭이 하나일 경우에만 arr[cnt]를 1로 설정해주니까 정답되네요

감사합니다!

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

문제

문제

출처

ICPC

제가 해본 테스트케이스로는 어떤게 틀렸는지 못찾겠습니다. ㅜ

woon1113 6년 전 0

djm03178 6년 전 1

woon1113 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말