[BOJ][JAVA] 14502: 연구소

 

 

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

14502번: 연구소

---

푸는 동안 사고과정 및 개선점

전형적인 BFS/DFS문제였던 것 같은데 너무 어렵게 생각했었다. 

내 경우에는 벽을 둘 수 있는 모든 좌표값을 뽑아서 매 case 마다 BFS를 돌려 최대 안전영역 값을 검출하려고했는데, 가지치기 없이 모든 좌표를 넣어서 경우의 수를 돌려도 통과가 된다.

 

여기서 최적화를 조금 더 한다면 , 3중 포문 대신에 재귀로 조합을 뽑아내는 방식이 있을 것 같다.

내가 사용하는 조합 템플릿은 아래와 같다.

	static void combination(int start, int n, int r) {
		if (r == 0) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < n; i++) {
				if (v[i]) {
					sb.append(numbers[i]);
				}
			}
			return; // return안해도 되긴하는데 base case임을 알리는 방법.
		}

		for (int i = start; i < n; i++) {
			v[i] = true; // 중복없는 조합뽑기
			combination(i + 1, n, r - 1); // start를 하나 올리고, 남은 뽑을거를 하나 줄이면 됨.
			v[i] = false;
		}
	}

r이 뽑는 개수로 몇개 뽑을 지를 넣으면 다 뽑았을 때가 base case로 재귀를 끝내는 시점이 된다. 조합이 나온김에 순열도 같이 보면 

public static void perm(int depth) {
		if (depth == targetDepth) {
			// 이러면 다 찾은 것.
		}
		for (int i = 0; i < numbers.length; i++) {
			if (!v[i]) {
				// 이러면 중복없는 순열 뽑기
				v[i] = true;
				output[depth] = numbers[i];
				perm(depth + 1);
				v[i] = false;
			}
		}
	}

이렇게 요약할 수 있다.

순열, 조합까지는 이제 무리없이 건드릴 수 있는데, 부분집합은 아직 연습이 필요하다.

import java.util.*;
import java.io.*;

public class Main {
	static int[] di = { -1, 0, 1, 0 };
	static int[] dj = { 0, 1, 0, -1 };

	static int n;
	static int m;
	static int max;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int[][] map = new int[n][m];
		max = 0;
		List<int[]> blank = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		} // 1은 벽, 0은 빈칸, 2는 바이러스, 경계선도 벽으로 간주함
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 0) { // 바이러스 기준 탐색
					blank.add(new int[] { i, j });
				}
			}
		}
		// 이제 blank에서 3개 뽑으면 됨
		int len = blank.size();
//		for(int[] i: blank) {
//			System.out.println(Arrays.toString(i));
//		}

		for (int i = 0; i < len; i++) {
			int[] one = blank.get(i);
			for (int j = i + 1; j < len; j++) {
				int[] two = blank.get(j);
				for (int k = j + 1; k < len; k++) {
					int[] three = blank.get(k);
					int[][] copyMap = new int[n][m];
					copy(copyMap, map);
					copyMap[one[0]][one[1]] = 1;
					copyMap[two[0]][two[1]] = 1;
					copyMap[three[0]][three[1]] = 1;
					// 세 개를 골라서, 복사한 map에 넣고, bfs를 돌린다.
					bfs(copyMap);
				}
			}
		}

		System.out.println(max);
	}

	private static void copy(int[][] copy, int[][] map) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				copy[i][j] = map[i][j];
			}
		}
	}

	private static void bfs(int[][] copy) {
		LinkedList<int[]> q = new LinkedList<>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (copy[i][j] == 2) {
					q.add(new int[] { i, j });
				}
			}
		}

		while (!q.isEmpty()) {
			int[] cur = q.pollFirst();
			for (int i = 0; i < 4; i++) {
				int ni = di[i] + cur[0];
				int nj = dj[i] + cur[1];
				if (ni < n && nj < m && ni >= 0 && nj >= 0 && copy[ni][nj] == 0) {
					q.add(new int[] { ni, nj });
					copy[ni][nj] = 2;
				}
			}
		}
		int safe = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (copy[i][j] == 0) {
					safe++;
				}
			}
		}
		max = Math.max(max, safe);
	}
}

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^