코드업 2062번

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

https://codeup.kr/problem.php?id=2062&rid=23688 

Up 2

---

문제 설명

 

재현이는 Up 1 문제에서 자기의 집을 띄우는데 성공하였다!

하지만 헬륨이 빠지면서 집은 다시 땅으로 내려오게 되었다.

헬륨이 왜 빠졌는지를 보자 풍선의 위치가 문제인 것을 알게 되었다.

지붕에는 층이 있다. 층은 0부터 9까지이다.

재현이는 지붕의 0층에 모든 풍선을 달자 연결부위가 약해져서 풍선이 날아간 것으로 추측한다.

재현이는 그래서 각 층에는 서로 최대한 많이 연결되어 있는 곳에만 풍선을 달려고 한다.

---

입력

 

첫번째 줄에 m, n이 입력된다. (1<=m, n<=19)

두번째 줄에 지붕의 지도가 m*n 형식으로 입력된다.

숫자는 층이고 -1은 풍선을 달 수 없는 곳이다.

---

출력

 

풍선의 최대수를 각 층마다 출력한다.

0개인 층은 출력하지 않아도 된다. 또한, 층은 오름차순으로 출력한다.

문제를 해석을 해보자면, 0부터 9까지 각 숫자들이 가장 많이 모여있는 영역을 찾아 몇개가 모여있는지를 출력해야 합니다. 이 문제를 어떻게 해결할까 고민하다가, 한 칸에서 시작해서 상, 하, 좌, 우의 칸으로 옮겨가며 처음 시작한 칸과 같은 숫자인지 판단하는 탐색을 모든 칸에서 실행해보는 방식으로 해결해보고자 하였습니다.

 

바로 순서도를 짜보았습니다.

이것은 대략적인 전체 과정의 순서도이고,

이것은 핵심이 되는 탐색 함수의 순서도입니다. 옆칸으로 이동하는 방식을 재귀함수를 이용하여 설계해보았습니다.

순서도를 바탕으로 바로 코드를 짜봅시다.

#include <stdio.h>

int a[20][20];

int num[10];

int cnt = 0;

int m, n;

void f(int flr, int x, int y)
{
	if(a[x][y] == flr)
	{
		cnt++;
		if(x-1 >= 0)
		{
			f(flr, x-1, y);
		}
		if(y-1 >= 0)
		{
			f(flr, x, y-1);
		}
		if(x+1 < m)
		{
			f(flr, x+1, y);
		}
		if(y+1 < n)
		{
			f(flr, 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 fn = 0; fn < 10; fn++)
	{
		for(int i = 0; i < m; i++)
		{
			for(int j = 0; j < n; j++)
			{
				cnt = 0;
				f(fn, i, j);
				num[fn] = num[fn]>cnt?num[fn]:cnt;
			}
		}
	}
	
	for(int fn = 0; fn < 10; fn++)
	{
		if(num[fn] != 0)
		{
			printf("%d %d\n", fn, num[fn]);
		}
	}
}

순서도대로 위와 같이 코드를 짜니, 시간초과가 뜨더군요. 왜 그런지 살펴보았더니, 이미 확인한 칸이라는 사실을 알 수가 없어서 왔던 칸으로 되돌아 가고, 다시 옆 칸으로 이동하고를 반복해서 발생한 일이었습니다. 그래서 한번 확인한 칸은 -1로 바꾸어 탐색을 완료했다는 사실을 표시해주었습니다.

#include <stdio.h>

int a[20][20];

int num[10];

int cnt = 0;

int m, n;

void f(int flr, int x, int y)
{
	if(a[x][y] == flr)
	{
		a[x][y] = -1;
		cnt++;
		if(x-1 >= 0)
		{
			f(flr, x-1, y);
		}
		if(y-1 >= 0)
		{
			f(flr, x, y-1);
		}
		if(x+1 < m)
		{
			f(flr, x+1, y);
		}
		if(y+1 < n)
		{
			f(flr, 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 fn = 0; fn < 10; fn++)
	{
		for(int i = 0; i < m; i++)
		{
			for(int j = 0; j < n; j++)
			{
				cnt = 0;
				f(fn, i, j);
				num[fn] = num[fn]>cnt?num[fn]:cnt;
			}
		}
	}
	
	for(int fn = 0; fn < 10; fn++)
	{
		if(num[fn] != 0)
		{
			printf("%d %d\n", fn, num[fn]);
		}
	}
}

잘 작동하네요! 그러면 코드 설명을 간단히 해보도록 하겠습니다.

먼저 m*n 짜리 배열, 즉 지붕의 지도를 입력 받습니다. 그리고, 0부터 9층까지, 모든 칸에 대해서 한 번씩 탐색을 실행해봅니다. 탐색이 이루어지는 방식은, 어떤 칸에서 시작하여 그 칸이 탐색하던 층수라면 -1로 바꾸어 이미 확인한 칸임을 표시하고 상, 하, 좌, 우로 이동하여 다시 탐색을 진행합니다. 그렇게 하여 연속적으로 총 몇 칸을 탐색했는지 카운트하고, 각 층별로 최대 카운트를 찾아 배열에 저장합니다. 마지막으로 그 배열에서 카운트가 0이 아닌 것을 층수와 함께 출력하면 됩니다.

---

이렇게 코드업 2062번 문제를 풀이해보았습니다.