[백준 14502 / JAVA] 연구소

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

14502번: 연구소

 

이 문제는 옛날에 c++로 풀었던 문제이지만 푼지 시간도 오래 지났고 자바로 바꾼 김에 다시 풀어봤다.

 

DFS와 BFS를 모두 사용한다.

 

    static public void DFS(int x, int y, int[][] map, int index) {
        if (index < 3) {
            for (int i = x; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (i == x && j == 0) j = y;
                    if (map[i][j] == 0) {
                        map[i][j] = 1;
                        DFS(i, j, map, index + 1);
                        map[i][j] = 0;
                    }
                }
            }
        } else
            spread(map);
    }

DFS를 이용해 벽을 세우는 코드이다.

x와 y는 시작 좌표이다.

for문의 i와 j를 0부터 시작해도 답이 나오지만 DFS를 중복해서 호출을 너무 많이 해버릴꺼 같아

i는 x부터 시작하도록하고 j는 제일 처음만 y부터 시작하도록 했다.

 

위 코드대로 실행한다면 예제 1번을 기준으로 DFS가 7176번 반복되지만 반복문의 i와 j를 0부터 한다면 40496번 반복한다. 적지않은 수가 차이난다. 물론 둘다 정답으로 인정된다.

 

    static public void DFS(int[][] map, int index) {
        if (index < 3) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 0) {
                        map[i][j] = 1;
                        DFS(map, index + 1);
                        map[i][j] = 0;
                    }
                }
            }
        } else
            spread(map);
    }

전부 반복하는 경우의 코드이다.

 

위가 전부 반복하는 경우, 아래가 x, y를 이용하는 경우이다.

굳이 x, y 를 넣어서 까지 복잡하게 해서 줄일 정도는 아닐 수 있지만 코드 몇 줄 차이로 저정도 차이라면 난 쓸 것 같다.

 

    public static void spread(int[][] map) {
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        Queue<Pair> queue = new LinkedList<>();
        int x, y, nx, ny;
        int cnt = 0;
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] == 2) {
                    queue.add(new Pair(i, j));
                    cnt++;
                }
            }
        }

        initVisit();

        do {
            x = queue.peek().x;
            y = queue.peek().y;
            queue.remove();

            for (int i = 0; i < 4; i++) {
                nx = x + dx[i];
                ny = y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    if (map[nx][ny] == 0 && visit[nx][ny] == false) {
                        queue.add(new Pair(nx, ny));
                        visit[nx][ny] = true;
                        cnt++;
                    }
                }
            }
        } while (!queue.isEmpty());

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++)
                if (map[i][j] == 1) cnt++;
        }

        if (result < (N * M - cnt)) result = (N * M - cnt);
    }

바이러스를 확산하는 코드이다. BFS를 이용해 큐에 처음에 존재하던 바이러스를 넣고 이후 주변에 빈칸이 있다면 큐에 넣어준다. 큐가 빌 때까지 반복한다.

cnt는 안전지대를 구하기 위해 벽, 바이러스의 수를 구한다.

 

굳이 cnt를 사용하지 않고 map을 깊은 복사 해준 뒤 직접 수를 바꾸고 나중에 전부 세봐도 된다.

 

이후 전체 칸 수에서 cnt를 빼준 값이 안전지대의 수이다.

이 중 제일 큰 수를 출력한다.

 

반응형

 

전체코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M, result = 0;
    static int[][] map;
    static Boolean[][] visit;

    public static class Pair {
        int x, y;

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

    public static void initVisit() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visit[i][j] = false;
            }
        }
    }

    public static void spread(int[][] map) {
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        Queue<Pair> queue = new LinkedList<>();
        int x, y, nx, ny;
        int cnt = 0;
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] == 2) {
                    queue.add(new Pair(i, j));
                    cnt++;
                }
            }
        }

        initVisit();

        do {
            x = queue.peek().x;
            y = queue.peek().y;
            queue.remove();

            for (int i = 0; i < 4; i++) {
                nx = x + dx[i];
                ny = y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    if (map[nx][ny] == 0 && visit[nx][ny] == false) {
                        queue.add(new Pair(nx, ny));
                        visit[nx][ny] = true;
                        cnt++;
                    }
                }
            }
        } while (!queue.isEmpty());

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++)
                if (map[i][j] == 1) cnt++;
        }

        if (result < (N * M - cnt)) result = (N * M - cnt);
    }

    static public void DFS(int x, int y, int[][] map, int index) {
        if (index < 3) {
            for (int i = x; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (i == x && j == 0) j = y;
                    if (map[i][j] == 0) {
                        map[i][j] = 1;
                        DFS(i, j, map, index + 1);
                        map[i][j] = 0;
                    }
                }
            }
        } else
            spread(map);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][];
        visit = new Boolean[N][];
        for (int i = 0; i < N; i++) {
            map[i] = new int[M];
            visit[i] = new Boolean[M];
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        DFS(0, 0, map, 0);
        System.out.println(result);
    }

}