글 읽기 - 단지번호붙이기 질문입니다

qkrwldnjs929 8년 전 0

예제 입력에서는 sort가 제대로 동작하는데 아래처럼 입력데이터를 바꾸면
sort가 제대로 동작하지않는걸로 보이는데 그 이유를 모르겟습니다..
전에도 C++ 에서 sort사용할때 되다 안되다 하는 경우가 있엇는데
어느부분이 잘못됫는지 모르겟습니다..

7
0110100
0110101
1111101
0000111
0100000
0111110
0111000

#include <cstdio>
#include <queue>
#include <algorithm>

#define Y (y+dy[i])
#define X (x+dx[i])
using namespace std;

int graph[30][30];
int check[30][30];
int dy[4] = {0,0,-1,1};
int dx[4] = {-1,1,0,0};
int cnt_arr[300];
void bfs(int y, int x, int cnt){
	int i, j, k;
	int f,r;
	queue<pair<int, int> > q;
	check[y][x] = 1;
	q.push(make_pair(y,x));
	while(!q.empty()){
		cnt_arr[cnt] ++;
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for(i = 0 ; i < 4; i ++){
			if(graph[Y][X] && !check[Y][X]){
				check[Y][X] = 1;
				q.push(make_pair(Y, X));
			}
		}
	}
}
int main(){
	int n;
	int i, j, k;
	int cnt = 0;

	
	scanf("%d",&n);
	for(i = 1 ; i <= n ; i ++){
		for(j = 1 ; j <= n ; j ++){
			scanf("%1d",&graph[i][j]);
		}
	}
	for(i = 1 ; i <= n ; i ++){
		for(j = 1 ; j <= n ; j ++){
			if(graph[i][j] && !check[i][j]){
				bfs(i,j,cnt++);
			}
		}
	}
	printf("%d\n",cnt);
	sort(cnt_arr, cnt_arr + cnt - 1);
	for(i = 0 ; i < cnt ; i ++){
		printf("%d\n",cnt_arr[i]);
	}
	return 0;
}

flflds0811 8년 전 0

알고리즘 헤더파일에 있는 주소 기반 함수들은 보통 시작주소부터 끝나는 주소 전까지 입니다.
시작주소(이상) 끝주소(미만) 으로 볼 수 있습니다.

sort(a,b)의 적용범위는 [a,b) 와 같이 볼 수 있습니다.
그러므로 sort에서도 인자로 전달되는 주소가 sort하고자 하는 범위의 시작주소와 마지막주소+1로 하여야 합니다.
그렇기 때문에 일반적인 배열 방식에서는
배열의 이름(시작주소), 배열의 이름+ 크기 (마지막 인덱스 다음 주소) 를 넘겨주어야 합니다
그러므로
sort(cnt_arr,cnt_arr+cnt) 로 작성하셔야 할 것 같습니다.
보통 벡터의 경우
sort(벡터.begin(),벡터.end()) 로 하는데
벡터에서는 begin은 첫 주소지만 end는 마지막 원소의 다음 주소를 가르키기 때문에 이와같이 인자로 넘겨줍니다.

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

문제

문제

출처

ICPC

단지번호붙이기 질문입니다

qkrwldnjs929 8년 전 0

flflds0811 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말