글 읽기 - 채점 중 60%에서 에러납니다. 반례 좀 도와줴요

wlsgussla123 6년 전 0

60%에서 실패합니다..ㅠㅠㅠ

다른 질문에 있는 반례는 정상작동을 하는데.. 무엇이 문제일까요?

고수님들 도와주세요!

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> answer;

int visit[100][100] = { 0, };
int answer_map[100][100] = { 0, };
int map[100][100] = { 0, };
int M, N; // map size
int K; // 직사각형 개수

int lx, ly, rx, ry; // 좌표

// 동 서 남 북
int row_dir[4] = { 0, 0, 1, -1 };
int col_dir[4] = { 1, -1, 0, 0 };

// DFS와 BFS.. 뭘 선택해야 할까? BFS로 했다가 안 된다는 걸 느끼고 DFS로 바꿔서 풀었다.
void DFS(int row, int col, int cnt) {
	visit[row][col] = 1;
	answer_map[row][col] = cnt;

	for (int i = 0; i < 4; i++) {
		if (row + row_dir[i] >= 0 && row + row_dir[i] < M && col + col_dir[i] >= 0 && col + col_dir[i] < N) {
			if (!visit[row + row_dir[i]][col + col_dir[i]] && !map[row + row_dir[i]][col + col_dir[i]]) {
				DFS(row + row_dir[i], col + col_dir[i], cnt);
			}
		}
	}
}

int main(void) {
	int cnt = 1;

	// M : 행, N : 열
	scanf("%d %d", &M, &N);
	scanf("%d", &K);
	
	for (int i = 0; i < K; i++) {
		scanf("%d %d %d %d", &lx, &ly, &rx, &ry);

		// 180도로 돌려도 똑같기 때문에 굳이 input을 맞출 필요가 없다.
		for (int j = ly; j < ry; j++) {
			for (int k = lx; k < rx; k++) {
				map[j][k] = -1;
				answer_map[j][k] = -1;
			}
		}
	}

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (!map[i][j] && !visit[i][j]) {
				DFS(i, j, cnt++);
			}
		}
	}

	for (int k = 1; k <= N; k++) {
		int count = 0;

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (answer_map[i][j] == k)
					count++;
			}
		}
		answer.push_back(count);
	}

	
	sort(answer.begin(), answer.end());
	printf("%d\n", cnt - 1);

	for (int i = 0; i < (int)answer.size(); i++) {
		if (answer[i] != 0) {
			printf("%d ", answer[i]);
		}
	}
	putchar('\n');

	return 0;
} 

/*
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2
*/

artage7 6년 전 1

많은 풀이가 있겠지만 저는 BFS로 했네요

이유는 BFS는 자기 주변부터 탐색하니깐 문제 조건과 일치하니깐요

그런데 문제는 이 사과의 시작점이 여러개인건데요.

각각의 점에서 BFS를 돌리면 당연히 답을 구하기 힘들겠지요.

그러니 BFS큐에 시작할수 있는 사과의 지점을 모두 넣고 시작합니다.

그러면 문제 없겠지요.

몇번 가야 사과가 모두 익는지, 사과가 안익는 경우는 언제인지는 아실거라 생각되네요

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

문제

문제

출처

ICPC

채점 중 60%에서 에러납니다. 반례 좀 도와줴요

wlsgussla123 6년 전 0

artage7 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말