mingssssss

1. 문제

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

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static ArrayList<ArrayList<Integer>> list;
	static ArrayList<ArrayList<Integer>> check_list;
	static boolean[][] visited;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int answer;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		list = new ArrayList<>();
		check_list = new ArrayList<>();
		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			list.add(new ArrayList<>());
			check_list.add(new ArrayList<>());
		}

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int temp = Integer.parseInt(st.nextToken());
				list.get(i).add(temp);
				check_list.get(i).add(temp);
			}
		}
		// 입력 종료
		answer = 0;
		for (int a = 0; a < N; a++) {
			for (int b = 0; b < M; b++) {				
				
				if (list.get(a).get(b) == 0) {

					list.get(a).set(b, 1);

					for (int c = a; c < N; c++) {
						for (int d = 0; d < M; d++) {
							
							if (a == c && d <= b) {
								continue;
							}							

							if (list.get(c).get(d) == 0) {

								list.get(c).set(d, 1);

								for (int e = c; e < N; e++) {
									for (int f = 0; f < M; f++) {
										
										if (c == e && f <= d) {
											continue;
										}

										if (list.get(e).get(f) == 0) {

											list.get(e).set(f, 1);

											for (int l = 0; l < N; l++) {
												for (int k = 0; k < M; k++) {
													if (visited[l][k] == false && list.get(l).get(k) == 2) {
														bfs(l, k, N, M, list, visited);

													}
												}
											}

											int temp = check_zero(N, M, list);
											answer = Math.max(temp, answer);
											copy(N, M, list, check_list);
											list.get(a).set(b, 1);
											list.get(c).set(d, 1);
											visited = new boolean[N][M];
										}

									}

								}
							}
							copy(N, M, list, check_list);
							list.get(a).set(b, 1);
							visited = new boolean[N][M];
						}
					}
				}
				copy(N, M, list, check_list);
				visited = new boolean[N][M];

			}
		}
		System.out.println(answer);

//		// 출력
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < M; j++) {
//				System.out.printf("%d ", check_list.get(i).get(j));
//			}
//			System.out.println();
//		}

	}

	private static void bfs(int r, int c, int N, int M, ArrayList<ArrayList<Integer>> list, boolean[][] visited) {

		Queue<int[]> q = new LinkedList<>();

		q.add(new int[] { r, c });
		visited[r][c] = true;

		while (!q.isEmpty()) {

			int[] now = q.poll();

			for (int i = 0; i < 4; i++) {

				int nextX = now[0] + dx[i];
				int nextY = now[1] + dy[i];

				if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
					continue;
				}

				if (visited[nextX][nextY] == true || list.get(nextX).get(nextY) == 1) {
					continue;
				}

				visited[nextX][nextY] = true;
				list.get(nextX).set(nextY, 2);
				q.add(new int[] { nextX, nextY });

			}

		}
	}

	private static int check_zero(int N, int M, ArrayList<ArrayList<Integer>> list) {

		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (list.get(i).get(j) == 0) {
					cnt++;
				}
			}
		}
		return cnt;
	}

	private static void copy(int N, int M, ArrayList<ArrayList<Integer>> list,
			ArrayList<ArrayList<Integer>> check_list) {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				list.get(i).set(j, check_list.get(i).get(j));
			}
		}

	}

}

3. 리뷰

브루트포스 알고리즘과 bfs를 이용한 탐색 문제이다.

2가 있는 상하좌우가 바이러스가 퍼진다고 했을 때, 벽을 임의로 반드시 3개를 세워

바이러스가 최소한으로 퍼지게(0의 개수가 가장 많게) 하는 문제이다.

임의로 벽을 3개 세운다는 개념 자체가 생소했다.

지금까지는 다 주어진 상태에서 탐색만 하면 됐는데, 지금은 내가 임의로 벽을 세워

가장 최소한의 값이 무엇인지(0의 개수가 최대한)구하는 문제여서

처음에는 바이러스가 있는 위치 기준으로 상하좌우를 탐색해서 바이러스 근처를

막아버리는 방법을 생각했으나, 예시에서 본 바와 같이 그런 경우로 풀 수 없는 상황이

발생했다.

따라서 벽 3개를 전체 맵에 순서대로 세운 다음
ex) [ (0, 0), (0, 1), (0, 2) ] , [ (0, 0), (0, 1), (0, 3) ],
[ (0, 0), (0, 1), (0, 4) ], [ (0, 0), (0, 1), (0, 5) ] ...

[ (N, M - 2), (N, M - 1), (N, M) ] 까지 벽이 세워질 때마다 bfs를 돌리는

방법을 생각했다.

시간과 메모리 모두 넉넉해서 바로 구현에 들어갔다.

2차원 배열에 벽을 순서대로 세우는 방법이 쉽지 않았다.

재귀나 다른 방법으로 많이들 풀었는데, 직관적이지 않고 익숙하지가 않아서

직접 벽을 세우는 방법을 택했다.

맨 처음 2중 포문은 첫 번째 벽이 세워지는 경우이다.

(0, 0)부터 탐색을 시작하면서 해당 좌푯값이 0이면 그 자리에서 멈추고 1로 바꾼다.

그 후 2중 포문은 두 번째 벽이 세워지는 경우이다.

만약 두 번째 벽의 2중 포문의 행이 첫 번째 벽의 2중 포문의 행과 같다면,

두 번째 벽의 2중 포문의 열은 첫 번째 2중 포문의 열보다 뒤에 있어야 하므로

체크해줘서 continue하게 했다. (핵심)

세 번째 벽의 2중 포문을 돌리면서 마찬가지의 조건을 넣었다.

이렇게 하면 벽이 순서대로 세워지게 된다.

세 번째 벽의 2중 포문을 돌리면서 세 번째 벽이 세워질 때마다

방문하지 않고, 해당 자리가 2라면(바이러스) bfs를 돌렸다.

bfs를 전부 돌렸다면, 해당 리스트는 바이러스가 전파된 상태이다.

이 상태에서 list에 0이 몇 개 있는지 따로 함수를 만들어서 확인하고,

매 bfs마다 0의 최댓값을 찾기 위해 Math.max()를 사용해서 체크했다.

이렇게 되면 세 번째 벽이 세워진 상태에서 list가 손상이 됐으므로,

새로 벽을 세우기 위해 기존에 있던 list를 초기의 list로 바꿔줘야 한다.

이 역시 다양한 방법이 있었지만, 따로 함수를 만들어 2중 포문으로 원래 리스트로

다시 복사해서 초기화했다.

초기화 한 경우에는 첫 번째와 두 번째 벽이 세워지지 않았으므로,

첫 번째 벽과 두 번째 벽을 초기화 한 다음 함수 뒤에 써준다. (중요)

이런식으로 탐색을 끝내면 0의 최댓값이 나오게 된다.

브루트포스 알고리즘은 늘 구현하는 것이 쉽지가 않은 것 같다.

bfs 첫 골드 문제라 뿌듯하고, 시간을 많이 들인 만큼 얻은 것이 많은 문제 였다.