최적해를 구하는 문제
5. 단지 번호 붙이기
문제 | |
NxN크기의 정사각형 모양의 지도가 있다. 지도에서 0은 집 없음, 1은 집 있음을 나타낸다. 단지란 왼쪽, 오른쪽, 위쪽, 아래쪽으로 연결되어 있는 집들의 집합이다. 예를 들어, 다음 지도에서는 세 개의 단지가 있다. 각 단지의 크기는 7, 8, 9이다. 입력 데이터가 주어지면, 단지의 개수와 각 단지의 크기를 출력하는 프로그램을 작성하시오. | |
입력 방법 | 입력 예 (input.txt) |
첫줄에는 지도의 크기 N(100이하의 정수) 둘째 줄부터는 지도가 주어진다. | 7 0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 |
출력 방법 | 출력 예 (output.txt) |
첫줄에는 단지의 개수, 둘째 줄에는 각 단지의 크기를 오름차순으로 출력한다. | 3 7 8 9 |
www.koi4u.net
문제 출처 : 1997년 한국정보올림피아드 본선 초등부 1번 문제
-> 파일 입출력을 하지 않고, 예제로 주어진 값을 2 by 2배열에 넣고 계산했다.
출력부분에서 정렬도 하지 않았지만, 이 프로그램의 핵심은 배열을 순서대로 카운트 하면서,
1과 0을 판별해 내고 1일때 또다시 현재 위치에서 상,하,좌,우에 1이 있는지 검색하고 있다면 이동하고,
그 위치에서 또다시 검색하는 것이 핵심이다.
예를들어 1을 찾아서 우측으로 이동 했다면, 이동한 자리를 기준으로 또다시 상,하,좌,우를 검색해야 하므로
문제의 핵심은 재귀에 있다. 루프가 돌아가는 동안 읽었던 값에 표시를 해 둠으로써 다시 읽어버리는 오류를
미리 검색하여 제거해 주는데 있으며, 또한 루프를 빠져나왔다가 다시 들어갈때는 표시값을 변경함으로써,
그 표시값을 배열첨자로 하는 배열의 값이 달라지므로, 각 아파트 단지의 수는 그 배열의 전체크기가 되며,
각 단지의 세대수는 그 배열의 값이 되는 것이다.
아래 소스를 잘 살펴보기 바란다. -권용호- ㅋㅋㅋㅋㅋㅋ
*/
#include <stdio.h>
#define n 7 //가로세로 크기
int apt[7][7] = {{0, 1, 1, 0, 1, 0, 0},
{0, 1, 1, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 0, 1},
{0, 0, 0, 0, 1, 1, 1},
{0, 1, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 0},
{0, 1, 1, 1, 0, 0, 0}};
int danji_num = 10; //단지번호(1단지는 11, 2단지는 12)
int cnt; //단지당 세대수
void cell_del(int x, int y) //찾은 세대는 지움(중복계산 방지)
{
apt[x][y] = danji_num;//단지 번호를 붙여 버린다. 1단지면 11, 2단지면 12...
}
int get(int x, int y) //해당 좌표값을 가져옴
{
if(x<0 || y<0 || x>=n || y>=n)
return 99; //0과 1이 아닌 아무숫자나 리턴(에러처리)
return apt[x][y]; //배열값을 다시 리턴(해당 좌표값을 가져온다)
}
void cell_cnt(int x, int y) //단지당 세대수 카운트
{
cell_del(x, y); //일단 단지를 지운다.
if(get(x, y-1) == 1)
{//좌
cnt++;
cell_cnt(x, y-1);
}
if(get(x, y+1) == 1)
{//우
cnt++;
cell_cnt(x, y+1);
}
if(get(x+1, y) == 1)
{//하
cnt++;
cell_cnt(x+1, y);
}
if(get(x-1, y) == 1)
{//상
cnt++;
cell_cnt(x-1, y);
}
}
void print(int *danji_cnt)
{
printf("\n단지수 : %d\n", danji_num-10);
for(int i=0; i<(danji_num-10); i++)
printf("%d단지 세대수 : %d\n",i+1,danji_cnt[i]);
}
void main(void)
{
int danji_cnt[100]={0};
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(apt[i][j] == 1) //세대가 있으면
{
danji_num++; //1단지는 11, 2단지는 12
cnt = 1; //이미 세대를 하나 찾았으므로 세대수 초기값은 1
cell_cnt(i,j); //단지내의 세대수를 카운트
danji_cnt[danji_num-11]=cnt;
}
}
}
print(danji_cnt); //결과출력
}