7733

static list<pair<int, int>> table[101];
static int board[100][100] = { 0, };
static int visit[100][100] = { 0, };

static void travel(int N, int y, int x)
{
	if (x < 0 || x >= N) //out of bound
		return;
	if (y < 0 || y >= N) //out of bound
		return;
	if (visit[y][x] || !board[y][x]) //visit or eliminated
		return;

	visit[y][x] = 1;
	travel(N, y - 1, x); //up
	travel(N, y + 1, x); //down
	travel(N, y, x - 1); //left
	travel(N, y, x + 1); //right;
}

static int __solution(int N)
{
	int ret = 0;
	for (int y = 0; y < N; y++) //full investigation
	{
		for (int x = 0; x < N; x++)
		{
			if (board[y][x] != 0 && !visit[y][x]) //exist and not-visited 
			{
				ret += 1; //number of group,
				travel(N, y, x);
			}
		}
	}

	memset(visit, 0, sizeof(int) * 100 * 100);
	return ret;
}

static int solution(void)
{
	int N, v, max = 1, total;
	scanf("%d", &N);

	total = N * N;
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			scanf("%d", &v);
			board[y][x] = v;
			table[v].push_back(pair<int, int>(y, x));
		}
	}

	for (int i = 1; total > 0 && i <= 100; i++)
	{
		list<pair<int, int>> &cur = table[i];
		int size = cur.size();

		while (!cur.empty())
		{
			pair<int, int> &pos = cur.front();
			board[pos.first][pos.second] = 0; //update
			cur.pop_front();
		}

		if (size)
		{
			total -= size;
			v = __solution(N);
			max = (v > max) ? v : max;
		}
	}

	memset(board, 0, sizeof(int) * 100 * 100);
	return max;
}

 

알고리즘 문제 풀이 시 에 나는 디버깅 시 내가 짠 코드를 이해하기 쉽게 가급적 함수를 많이 정의하는 편이다.

그런데 여기서 중요한 점은 인자 전달을 가급적 최소화 하는 방향으로 해야한다는 점이다.

최초로 작성한 코드는 visit이라는 배열을 __solution() 에서 생성하여 인자로 넘기는 식이 었다.

물론 답은 맞았지만 문제는 메모리 사용량과 시간이었고 아래와 같다.

 

메모리(29,112 kb), 실행시간(205 ms)

 

제시한 코드의 메모리와 실행시간은 아래와 같다.

 

메모리(13,072 kb), 실행시간(148 ms)

 

딱 봐도 큰 차이가 있다는 것을 알 수 있고, 이러한 이유는 코드 구조 상 재귀 호출로 인하여 인자에 대한 메모리 역시 스택에 쌓이기 때문이다. 

즉, 인자를 위한 메모리 할당을 줄였고, 또 할당받은 메모리에 값을 대입할 필요가 없기 때문에 실행시간 역시 줄어든 것이라 볼 수 있다.

여기서 N이라는 변수 역시 전역으로 두면 더 줄일 수 있으리라 생각한다.

 

문제에 대한 풀이는 아래와 같다.

 

travel을 한번 하고 나면 덩어리 개수를 구할 수 있다.

그래서 제거된 치즈 말고 아직 남아있는 치즈들을 모두 방문 할 때 까지,

travel을 반복하는 것이다.