백준 14502 풀이

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

연구소

연구소 문제다. 바이러스가 퍼지는 것연구소 문제다. 바이러스가 퍼지는 것은 bfs로 처리할 수 있다.

문제에서 벽을 3개를 치고 바이러스가 전파되었을 때 안전지대의 개수를 구하는 것인데 하나하나 살펴보자.

1. 벽을 3개 세운다. 이때 벽을 세울 수 있는 곳은 0인 곳이다.
   1-1. 따라서 0인 모든 곳에 벽을 세워본다.(완전탐색)
2. 바이러스(2)의 위치를 찾아 전파(bfs)
3. 전파가 끝난 후 0의 개수를 구한다.
   3-1. 기존의 max와 새로 구한 cnt 값을 비교, 큰 값을 max로 한다.

이 때 완전 탐색이기 때문에 입력받은 그래프를 그대로 사용하면 안되고 그래프를 카피해서 사용해야한다.(initLab)

나같은 경우 0인 곳에 벽을 세워야는데 이를 어떻게 처리할지 고민하다가 그냥 그래프에서 0인 곳의 좌표를 리스트에 저장해 반복시켰다.

문제를 푸는데 지장은 없었지만 메모리가 조금 빡빡하게 주어졌거나 제한 시간이 작다면 좀 무리가 있을지도 모르겠다.

그래서 다른 사람이 작성한 코드를 확인하니 벽을 세우는 것을 재귀함수로 처리했더라...
이런 부분에서 많이 부족하지 않았나싶다.

또 이렇게 하니 벽을 3개 세우고 3중 for문이었는데 내부 for문 한 번이 끝날때마다 initLab()을 계속 호출해줘야 해서 이 부분이 조금 마음에 안든다.

재귀로 했으면 이런 시간 낭비가 없지 않았을까 아쉽다.

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static boolean visit[][];
    static int n, m;
    static int graph[][];
    static int max = -1;
    static int[][] lab;
    static ArrayList<Pair> wallList;
    static Queue<Pair> queue;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] num = br.readLine().split(" ");
        n = Integer.parseInt(num[0]);
        m = Integer.parseInt(num[1]);
        graph = new int[n][m];
        visit = new boolean[n][m];
        wallList = new ArrayList<>();
        queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            String[] tmp = br.readLine().split(" ");
            for (int j = 0; j < tmp.length; j++) {
                graph[i][j] = Integer.parseInt(tmp[j]);
            }
        }

        lab = new int[graph.length][graph[0].length];

        findZero();

        for (int i = 0; i < wallList.size() - 2; i++) {
            initLab();
            Pair pi = wallList.get(i);
            lab[pi.x][pi.y] = 1;
            for (int j = i + 1; j < wallList.size() - 1; j++) {
                Pair pj = wallList.get(j);
                lab[pj.x][pj.y] = 1;
                for (int k = j + 1; k < wallList.size(); k++) {
                    Pair pk = wallList.get(k);
                    lab[pk.x][pk.y] = 1;
                    findVirus();
                    bfs();
                    int cnt = calcZero();
                    if (cnt > max) {
                        max = cnt;
                    }
                    initLab();
                    lab[pi.x][pi.y] = 1;
                    lab[pj.x][pj.y] = 1;
                }
                initLab();
                lab[pi.x][pi.y] = 1;            }
        }

        bw.write(max + "\n");
        br.close();
        bw.close();
    }

    private static void findZero() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j] == 0) {
                    Pair p = new Pair(i, j);
                    wallList.add(p);
                }
            }
        }
    }

    private static void initLab() {
        for (int i = 0; i < lab.length; i++) {
            System.arraycopy(graph[i], 0, lab[i], 0, graph[0].length);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                visit[i][j] = false;
        }
    }

    private static void findVirus() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (lab[i][j] == 2) {
                    queue.offer(new Pair(i, j));
                }
            }
        }
    }

    private static void bfs() {
        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            visit[p.x][p.y] = true;
            for (int i = 0; i < 4; i++) {
                if ((p.x + dx[i] >= 0 && p.x + dx[i] <= n - 1) && (p.y + dy[i] >= 0 && p.y + dy[i] <= m - 1)) {
                    if (lab[p.x + dx[i]][p.y + dy[i]] != 1 && !visit[p.x + dx[i]][p.y + dy[i]]) {
                        lab[p.x + dx[i]][p.y + dy[i]] = 2;
                        queue.offer(new Pair(p.x + dx[i], p.y + dy[i]));
                    }
                }
            }
        }
    }

    private static int calcZero() {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (lab[i][j] == 0)
                    count++;
            }
        }
        return count;
    }
}

class Pair {
    public int x;
    public int y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

정리

• initLab() : 완전탐색이기때문에 매 사이클마다 초기화를 시켜줘야한다.
• findVirus() : 완전 비효율적인 함수였다. 생각해보니 처음 한번만 호출해줘도 바이러스의 위치는 바뀌지 않기때문에 매 사이클마다 호출 안해줘도 될 것 같다.
• bfs() : 바이러스를 퍼트린다.
• calcZero() : 바이러스 전파가 끝난 후 안전지대(0)의 개수를 구한다.