코드업 2062

이번 글에서는 코드업 2062문제를 풀어보겠습니다.

 

재현이는 Up 1 문제에서 자기의 집을 띄우는데 성공하였다!
하지만 헬륨이 빠지면서 집은 다시 땅으로 내려오게 되었다.
헬륨이 왜 빠졌는지를 보자 풍선의 위치가 문제인 것을 알게 되었다.
지붕에는 층이 있다. 층은 0부터 9까지이다.
재현이는 지붕의 0층에 모든 풍선을 달자 연결부위가 약해져서 풍선이 날아간 것으로 추측한다.
재현이는 그래서 각 층에는 서로 최대한 많이 연결되어 있는 곳에만 풍선을 달려고 한다.

입력
첫번째 줄에 m, n이 입력된다.(1<=m,n<=19)
두번째 줄에 지붕의 지도가 m*n형식으로 입력된다.
숫자는 층이고 -1은 풍선을 달 수 없는 곳이다.

출력
풍선의 최대수를 각 층마다 출력한다.
0개인 층은 출력하지 않아도 된다. 또한, 층은 오름차순으로 출력한다.

 

1. 문제분석

이 문제는 주어진 2차원 배열에서 상하좌우로 숫자가 최대한 많이 이어진 개수를 세면 되는 문제입니다.

 

 

 

2. 알고리즘 설계

 

3. 코딩

함수 f에 층수와 배열에서 그 값의 위치를 입력한 후 값의 상하좌우 값을 탐색해보았다.

배열의 범위 안에 있을 때 조건에 따라 f에 다시 값을 넣어주면서 c를 더해주었다.

 

층수만큼 반복하고 모든 칸을 탐색하기 위해 반복하면서 그 값을 배열 num에 저장하고 

나중에 출력해주었다.

 

[문제해결]

처음에 코딩했을 때 

함수 f에서 탐색한 배열 값을 -1로 바꾸어 주지 않아 계속 반복되면서 오류가 났었고

main 함수에서 f 실행전 c를 초기화하지 않아 오류가 나게 되었다.

#include <stdio.h>

int a[20][20];
int num[10];
int c=0;
int m, n;

void f(int p, int x, int y){
	if(a[x][y]==p){
		c++;
		if(x-1>=0) f(p, x-1, y);
		if(y-1>=0) f(p, x, y-1);
		if(x+1<m) f(p, x+1, y);
		if(y+1<n) f(p, x, y+1);
	}
	else return;
}

int main(){
	scanf("%d %d", &m, &n);
	for(int i=0; i<m; i++{
		for(int j=0; j<n; j++){
			scanf("%d", &a[i][j]);
		}
	}
	
	for(int k=0; k<10; k++){
		for(int i=0; i<m; i++){
			for(int j=0; j<n; j++){
				f(k, i, j);
				num[k] = num[k]> c? num[k]:c;
			}
		}
	}
	
	for(int k=0; k<10; k++){
		if(num[k]!=0){
			printf("%d %d\n", k, num[k]);
		}
	}
}

 

이를 수정하여 다시 코드를 짰고 실행되는 것을 확인하였다.