글 읽기 - 마지막에 ans배열 sort하는 이유?

dhin131 6년 전 0

단지붙이기 문제 정답 코드입니다만

마지막에 각 단지의 개수가 담긴 ans배열을 sort하는 과정이 없으면 틀렸습니다로 뜨더군요.

그런데 ans 배열의 인덱스가 곧 단지번호이기 때문에 sort과정이 정답에 영향을 끼치지 않는다고 생각되는데

어째서 채점의 정답여부를 판가름짓는지요?

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int a[30][30];
int b[30][30];
int ans[25 * 25] = { 0 };
int n;
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { -1, 0, 1, 0 };

void bfs(int x, int y, int cnt) {

	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	b[x][y] = cnt;
	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 (0 <= nx && nx < n && 0 <= ny && ny < n) {
				if (a[nx][ny] == 1 && b[nx][ny] == 0) {
					q.push(make_pair(nx, ny));
					b[nx][ny] = cnt;
				}
			}
		}
	}
}


int main() {

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%1d", &a[i][j]);
		}
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (a[i][j] == 1 && b[i][j] == 0) {
				bfs(i, j, ++cnt);				
			}
		}
	}
	printf("%d\n", cnt);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ans[b[i][j]] += 1;
		}
	}	

	sort(ans + 1, ans + cnt + 1); // 여기서 왜 sort하는 과정이 필요한지?
    
	for (int i = 1; i <= cnt; i++) {
		printf("%d\n", ans[i]);
	}

	return 0;
}

simm4256 6년 전 1

문제를 다시 읽어보세요.

단지 내 아파트 개수를 오름차순으로 출력하시오

라고 되어있습니다.

dhin131 6년 전 0

앗 이해하였습니다. 단지 1의 개수, 단지 2의 개수 순으로 출력하는 것으로 착각하였군요.

앞으로는 문제를 주의해서 읽도록 하겠습니다. 감사합니다.

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

문제

문제

출처

ICPC

마지막에 ans배열 sort하는 이유?

dhin131 6년 전 0

simm4256 6년 전 1

dhin131 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말