[골드 4] 연구소

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

14502번: 연구소

벽을 어떻게 세워야 하는 걸까 규칙이 있나?

 

그냥 모든 경우의 수를 세어보자

1. 벽 3개 세우므로 3중 for문

2. 바이러스 퍼지게 하기 2중 for문 bfs

3. 안전공간 세기 2중 for문

 

*실수한 점 바이러스 퍼지게 하는 건 가짜 tmp_graph 했는데

tmp_graph = graph로 하니 얕은 복사로 주소값이 복사되어 graph가 망가진다

직접 2중 for문으로 값 자체 옮겨야 함 

 

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N, M;
        int[][] graph;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++)
                graph[i][j] = Integer.parseInt(st.nextToken());
        }


        ///////////////////////////////////////////////////////////////////////////

        int max = 0;

        for (int i = 0; i < N * M; i++) {
            if (graph[i / M][i % M] != 0)
                continue;

            graph[i / M][i % M] = 1;

            for (int j = 0; j < N * M; j++) {
                if (graph[j / M][j % M] != 0)
                    continue;

                graph[j / M][j % M] = 1;

                for (int k = 0; k < N * M; k++) {
                    if (graph[k / M][k % M] != 0)
                        continue;

                    graph[k / M][k % M] = 1;

                    int[][] tmp_graph = new int[N][M];

                    for (int v = 0; v < N; v++) {
                        for (int h = 0; h < M; h++) {
                            tmp_graph[v][h] = graph[v][h];
                        }
                    }


                    for (int v = 0; v < N; v++) {
                        for (int h = 0; h < M; h++) {
                            bfs(tmp_graph, v, h);
                        }
                    }

                    int count = 0;

                    for (int v = 0; v < N; v++) {
                        for (int h = 0; h < M; h++) {
                            if (tmp_graph[v][h] == 0) count++;
                        }
                    }

                    if (max < count) max = count;

                    graph[k / M][k % M] = 0;

                }

                graph[j / M][j % M] = 0;
            }

            graph[i / M][i % M] = 0;
        }

        sb.append(max);
        System.out.println(sb);


    }

    public static void bfs(int[][] graph, int v, int h) {


        if (graph[v][h] == 2) {
            if (v != 0 && graph[v - 1][h] == 0) {
                graph[v - 1][h] = 2;
                bfs(graph, v - 1, h);
            }
            if (v != graph.length - 1 && graph[v + 1][h] == 0) {
                graph[v + 1][h] = 2;
                bfs(graph, v + 1, h);
            }
            if (h != 0 && graph[v][h - 1] == 0) {
                graph[v][h - 1] = 2;
                bfs(graph, v, h - 1);
            }
            if (h != graph[v].length - 1 && graph[v][h + 1] == 0) {
                graph[v][h + 1] = 2;
                bfs(graph, v, h + 1);
            }
        }

    }
}