[Baekjoon]14502.연구소

14502.연구소

 http://www.acmicpc.net/problem/14502

---

삼성 SW역량테스트 기출문제였다고 한다. 완전탐색+dfs or bfs 의 문제라고 생각했다. 먼저 구조를 생각해보면 

1. 벽을 3개 세운다.
2. 바이러스를 퍼뜨린다.
3. 안전영역의 개수를 센다.
4. 최댓값인지 확인하고 아니면 1로 돌아가서 반복. 최댓값이면 리턴.

여기서 벽을 3개 세우는 것이 문제였다.  map에서 0인 부분에서 3개를 골라서 벽을 세워야 하므로 조합개념을 사용해야 했다. 2차원 배열에서 모든 좌표를 다 해보는 방법을 몰라서 찾아본 결과 다음과 같은 방법으로 모든 좌표를 탐색할 수 있었다.

 

N*M 2차원 배열이 주어졌을때 N*M개 중에서 3개를 뽑는다고 생각하면 된다.

i를 0~N*M 까지 증가시키면서 (i/M, i%M) 을 하면 모든 인덱스를 방문할 수 있다.

예를 들어 N=3, M=2 인 2차원배열이 있으면

이와 같은 방법으로 모든 좌표를 탐색할 수 있다. 

벽을 3개 세우는 모든 경우를 다 해봐야 하므로 벽을 3개 세운 상태의 맵을 따로 저장할 필요가 있다. 이를 위해서 copyMap메소드로 맵을 복사하고 복사한 맵에서 바이러스를 퍼뜨린다. 

private static void buildWall(int start, int cnt) {

		if (cnt == 3) { // 벽이 3개 세워지면 tempMap에 복사하고 바이러스 퍼뜨림.
			copyMap(map, tempMap);
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (tempMap[i][j] == 2) {
						spreadVirus(i, j);
					}
				}
			}

			ans = Math.max(ans, getSafetyArea(tempMap));
			return;
		}

		for (int i = start; i < N * M; i++) { // 벽세우기.
			int x = i / M;
			int y = i % M;
			if (map[x][y] == 0) {
				map[x][y] = 1;
				buildWall(i + 1, cnt + 1);
				map[x][y] = 0;
			}
		}
	}

spreadVirus메소드는 일반적인 dfs알고리즘과 같은 방법으로 구현했다. 탐색을 재귀적으로 수행하는 메커니즘에 대한 이해가 더 필요할 것 같다. 

 

<전체코드>