글 읽기 - 반례도 다 맞다고 나오는데 왜 틀렸는지 모르겠습니다.

myabc17 5년 전 0

질문게시판에 있는 반례도 입력해봤는데 결과가 잘나옵니다.

근데 제출만 하면 틀렸습니다가 뜨길래 어디가 틀린지 잘 모르겠습니다. 흑흑 ㅠㅠㅠ

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

using namespace std;

int N;
int visit[26][26] = { { 0, } };
int map[26][26];
int home_count[100];
queue<pair<int, int>> q;

int x_pos[4] = { 0, 1, 0, -1 };
int y_pos[4] = { 1,0,-1,0 };

// x, y 범위검사
bool is_range(int x, int y)
{
	if (x < 0 || x >= N || y < 0 || y >= N)
		return false;
	return true;
}

int bfs()
{
	int i, j, count = 0;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			// 들린적이 없는데 1이 있는경우 들어가서 bfs 돌린다.
			if (map[i][j] == 1 && visit[i][j] == 0) {
				pair<int, int> p = make_pair(j, i);
				q.push(p);
				visit[i][j] = 1;
				home_count[count] += 1; // 단지마다 집의 개수

				while (!q.empty()) {
					p = q.front();
					q.pop();
					int m = p.first;
					int n = p.second;

					for (int k = 0; k < 4; k++) {
						int x = m + x_pos[k];
						int y = n + y_pos[k];
						if (is_range(x, y)) {
							if (map[y][x] == 1 && visit[y][x] == 0) {
								visit[y][x] = 1;
								home_count[count] += 1; // 해당 단지의 집 개수 +1
								p = make_pair(x, y);
								q.push(p);
							}
						}
					}
				}
				count += 1; // 단지의 개수
			}
		}
	}
	return count;
}
int main() {
	cin >> N;
	if (N < 5 || N > 25)
		return 0;

	for (int i = 0; i < N; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < N; j++) {
			map[i][j] = temp[j] - 48;
		}
	}

	int count = bfs();
	cout << count << endl;

	// sort 함수가 있지만 그것때문에 오류난 사람도 있다고해서
	// 직접 정렬알고리즘 작성
	for (int i = 0; i < count; i++) {
		for (int j = i + 1; j < count; j++) {
			if (home_count[i] > home_count[j]) {
				int tmp = home_count[j];
				home_count[j] = home_count[i];
				home_count[i] = tmp;
			}
		}
	}

	// 단지마다 집 개수 출력
	for (int i = 0; i < count; i++)
		cout << home_count[i] << endl;
}

25
1100110011001100110011000
0011001100110011001100110
1100110011001100110011000
0011001100110011001100110
1100110011001100110011000
0011001100110011001100110
1100110011001100110011000
0011001100110011001100110
1100110011001100110011000
0011001100110011001100110
1100110011001100110011000
0011001100110011001100110
1100110011001100110011000
0011001100110011001100110
1100110011001100110011000
0011001100110011001100110
1100110011001100110011000
0011001100110011001100110
1100110011001100110011000
0011001100110011001100110
0011001100110011001100110
1100110011001100110011000
0011001100110011001100110
1100110011001100110011000
0011001100110011001100110

집이 100개 가 넘을 수 있습니다 ->위 TC 144개 나옵니다

djm03178 5년 전 0

바로 아래 질문에 왜 이게 안 되는지 써놓았습니다.

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

문제

문제

출처

ICPC

반례도 다 맞다고 나오는데 왜 틀렸는지 모르겠습니다.

myabc17 5년 전 0

seojeongwook2 5년 전 1

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말