14502번 연구소

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

14502번: 연구소

 

 

소스코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int m;
    static int[][] map;
    static int rx[] = {0, 0, -1, 1};
    static int ry[] = {-1, 1, 0, 0};

    static ArrayList<Node> virus;

    static class Node {
        int r, c;

        Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static int bfs(ArrayDeque <Node> block) {
        ArrayDeque<Node> deque = new ArrayDeque<>();
        int cMap[][] = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cMap[i][j] = map[i][j];
            }
        }
        for (Node node : block) {
            cMap[node.r][node.c] = 1;
        }
        for (Node v : virus) {
            deque.addLast(v);
            while (!deque.isEmpty()) {
                Node node = deque.pollFirst();
                for (int i = 0; i < 4; i++) {
                    int nx = node.r + rx[i];
                    int ny = node.c + ry[i];

                    if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if(cMap[nx][ny] != 0) continue;
                    cMap[nx][ny] = 2;
                    deque.addLast(new Node(nx, ny));
                }
            }
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(cMap[i][j] == 0) sum += 1;
            }
        }
        return sum;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        virus = 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());
                if (map[i][j] == 2) virus.add(new Node(i, j));
            }
        }

        int max = 0;
        ArrayDeque<Node> block = new ArrayDeque<>();
        for (int i = 0; i < n * m - 2; i++) {
            if (map[i / m][i % m] != 0) continue;
            block.addLast(new Node(i / m, i % m));
            for (int j = i + 1; j < n * m - 1; j++) {
                if (map[j / m][j % m] != 0) continue;
                block.addLast(new Node(j / m, j % m));
                for (int k = j + 1; k < n * m; k++) {
                    if (map[k / m][k % m] != 0) continue;
                    block.addLast(new Node(k / m, k % m));
                    max = Math.max(max, bfs(block));
                    block.pollLast();
                }
                block.pollLast();
            }
            block.pollLast();
        }
        bw.write(max + ""); bw.flush();
    }

}

 

 

해결방법

삼중 for문을 돌려 벽 3개가 세워지는 모든 경우의 수를 찾아 bfs()를 호출하였다. 이 부분이 상당히 헷갈렸다.

인자로 ArrayDeque를 보내면 당연히 복사한게 아니니까 poll()을 하면 없어지므로 다른 식으로 뽑아써야 하는데 바보처럼 poll()해서 시간을 엄청 날렸다.