[백준] 14502번 - 연구소 [Java]

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

 

[백준] 14502번 - 연구소 [Java]

[백준] 14502번 - 연구소 [Java]

[백준] 14502번 - 연구소 [Java]

---

1.  아이디어

 

주어진 빈 칸 중 세 개를 뽑아 벽으로 만들고 시뮬레이션을 돌린 후 다시 빈 칸으로 만드는 과정을 반복하면 해결할 수 있다. 벽을 정확히 3개를 세우면 돼서 3중 for문을 활용했고 시뮬레이션은 BFS 알고리즘을 활용했다.

---

2. 문제풀이

 

입력에서 빈칸과 바이러스의 위치는 각각 리스트에 저장 후 3중 for문으로 빈칸 리스트에서 3개를 뽑아 벽으로 바꾼 후 바이러스의 위치를 통해 BFS 알고리즘을 적용했다. 이후 벽을 빈 칸으로 바꿔주면 된다.

---

3. 코드

 

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

public class Main {

    private static class Node {
        int r;
        int c;

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

    private static final int BLANK = 0;
    private static final int WALL = 1;

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        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());

        int[][] map = new int[N][M];
        List<Node> blankList = new ArrayList<>();
        List<Node> virusList = new ArrayList<>();
        int wallCnt = 0;

        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] == BLANK) blankList.add(new Node(i, j));
                else if (map[i][j] == WALL) wallCnt++;
                else virusList.add(new Node(i, j));
            }
        }

        int max = 0;

        for (int i = 0; i < blankList.size() - 2; i++) {
            map[blankList.get(i).r][blankList.get(i).c] = WALL;

            for (int j = i + 1; j < blankList.size() - 1; j++) {
                map[blankList.get(j).r][blankList.get(j).c] = WALL;

                for (int k = j + 1; k < blankList.size(); k++) {
                    map[blankList.get(k).r][blankList.get(k).c] = WALL;

                    boolean[][] visited = new boolean[N][M];
                    int virusCnt = 0;
                    for (Node virus : virusList) {
                        if (visited[virus.r][virus.c]) continue;

                        virusCnt += bfs(virus, N, M, map, visited);
                    }

                    max = Math.max(max, N * M - wallCnt - 3 - virusCnt);

                    map[blankList.get(k).r][blankList.get(k).c] = BLANK;
                }
                map[blankList.get(j).r][blankList.get(j).c] = BLANK;
            }
            map[blankList.get(i).r][blankList.get(i).c] = BLANK;
        }

        System.out.println(max);
    }

    private static int bfs(Node start, int N, int M, int[][] map, boolean[][] visited) {
        Queue<Node> q = new ArrayDeque<>();
        q.add(start);

        visited[start.r][start.c] = true;

        int cnt = 1;

        while (!q.isEmpty()) {
            Node node = q.remove();

            for (int dir = 0; dir < 4; dir++) {
                int nr = node.r + dr[dir];
                int nc = node.c + dc[dir];

                if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
                if (map[nr][nc] != BLANK || visited[nr][nc]) continue;

                q.add(new Node(nr, nc));
                visited[nr][nc] = true;
                cnt++;
            }
        }

        return cnt;
    }

}

---

4. 후기