<BOJ> 17142 자바(연구소3)

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

Marina Bay Sands, Singapore

 

 

풀이 시간

 - 2.5h

 

풀이 방법 

- 조합(DFS) + BFS 를 이용해 풀어야 하는 문제다.

- 입력으로 주어지는 바이러스의 개수 만큼 오름차수 순열로 바이러스의 조합을 만들어준 뒤

- ArrayList에 담아둔 객체를 Q에 담아 BFS를 돌려주었다.

- emptyCount와 Count가 일치하는 지 확인하는 과정에서 최초 map의 원소가 빈칸인 경우에만 count를 +1 해주어야한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class b17142_연구소3 {
    static int N, M, emptyCount;
    private static int[][] map;
    private static int[][] dist;
    private static ArrayList<int[]> virusPoint;
    private static Queue<int[]> q = new LinkedList<>();
    private static boolean[] combiVisited;
    private static int[] dy = {-1, 1, 0, 0};
    private static int[] dx = {0, 0, -1, 1};
    private static int ans = Integer.MAX_VALUE;
    private static boolean[][] visited;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        virusPoint = new ArrayList<>();


        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if      (map[i][j] == 2) virusPoint.add(new int[]{i, j});
                else if (map[i][j] == 0) emptyCount++;
            }
        }

        if (emptyCount == 0) {
            System.out.println(0);
            return;
        }

        combiVisited = new boolean[virusPoint.size()];
        // 조합 만들고 bfs돌리기
        combination(new int[M], 0, 0);

        if (ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }

    }

    private static void combination(int[] combi, int start, int depth) {  // 오름차순 정렬을 위해 파라미터에 start 추가
        if (depth == M) {
            dist = new int[N][N];
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                Arrays.fill(dist[i], Integer.MAX_VALUE);
            }
            for(int i : combi){
                int[] point = virusPoint.get(i);
                q.add(point);
                dist[point[0]][point[1]] = 0;
                visited[point[0]][point[1]] = true;
            }
            bfs();
            return;
        }
        for (int i = start; i < virusPoint.size(); i++) {
            if(combiVisited[i]) continue;
            combiVisited[i] = true;
            combi[depth] = i;
            combination(combi,i +1, depth+1);
            combiVisited[i] = false;
        }

    }

    private static void bfs() {
        int count = 0;
        int max = Integer.MIN_VALUE;
        while (!q.isEmpty()) {
            int[] now = q.poll();
            for (int i = 0; i < 4; i++) {
                int ny = now[0] + dy[i];
                int nx = now[1] + dx[i];
                if (ny < 0 || ny >= N || nx < 0 || nx >= N || map[ny][nx] == 1 || dist[ny][nx] != Integer.MAX_VALUE || visited[ny][nx]) {
                    continue;
                }
                visited[ny][nx] = true;
                if(map[ny][nx]== 2) {
                    dist[ny][nx] = dist[now[0]][now[1]] +1;
                    q.add(new int[]{ny, nx});
                }
//                else if (dist[now[0]][now[1]] + 1 < dist[ny][nx]) {
                else {
                    dist[ny][nx] = dist[now[0]][now[1]] + 1;
                    count ++;
                    max = max > dist[ny][nx] ? max : dist[ny][nx];
                    q.add(new int[]{ny, nx});
                }
            }
        }
        if (emptyCount == count) {
            ans = ans < max ? ans : max;
        }

    }
}

 

 

코드 리뷰

1. 변수명 및 가독성: 변수명은 직관적으로 작성되었지만, 일부 변수명과 주석을 통해 코드의 가독성을 더욱 높일 수 있다.
2. 큐 초기화: BFS 함수 내에서 큐를 재사용할 때, 초기화가 누락된 부분이 있다.
3. 결과 출력 조건: 최종 결과 출력 부분에서 ans 값이 Integer.MAX_VALUE인 경우를 더 명확히 처리할 수 있다.
4. 자료구조 초기화: dist 배열과 visited 배열의 초기화는 combination 함수 내에서 수행하는 것이 적절하다.

 

개선된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class b17142_연구소3 {
    static int N, M, emptyCount;
    private static int[][] map;
    private static int[][] dist;
    private static ArrayList<int[]> virusPoint;
    private static boolean[] combiVisited;
    private static int[] dy = {-1, 1, 0, 0};
    private static int[] dx = {0, 0, -1, 1};
    private static int ans = Integer.MAX_VALUE;
    private static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        virusPoint = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 2) virusPoint.add(new int[]{i, j});
                else if (map[i][j] == 0) emptyCount++;
            }
        }

        if (emptyCount == 0) {
            System.out.println(0);
            return;
        }

        combiVisited = new boolean[virusPoint.size()];
        // 조합 만들고 bfs 돌리기
        combination(new int[M], 0, 0);

        if (ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }

    // 조합을 생성하는 DFS + 백트래킹 함수
    private static void combination(int[] combi, int start, int depth) {
        if (depth == M) {
            dist = new int[N][N];
            visited = new boolean[N][N];
            Queue<int[]> q = new LinkedList<>();  // BFS 큐 초기화

            for (int i = 0; i < N; i++) {
                Arrays.fill(dist[i], Integer.MAX_VALUE);
            }
            for (int i : combi) {
                int[] point = virusPoint.get(i);
                q.add(point);
                dist[point[0]][point[1]] = 0;
                visited[point[0]][point[1]] = true;
            }
            bfs(q);
            return;
        }
        for (int i = start; i < virusPoint.size(); i++) {
            if (combiVisited[i]) continue;
            combiVisited[i] = true;
            combi[depth] = i;
            combination(combi, i + 1, depth + 1);
            combiVisited[i] = false;
        }
    }

    // BFS를 이용한 바이러스 확산 및 최소 시간 계산 함수
    private static void bfs(Queue<int[]> q) {
        int count = 0;
        int max = 0;  // 초기값을 0으로 설정

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int y = now[0];
            int x = now[1];

            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];

                if (ny < 0 || ny >= N || nx < 0 || nx >= N || map[ny][nx] == 1 || visited[ny][nx]) {
                    continue;
                }

                visited[ny][nx] = true;
                dist[ny][nx] = dist[y][x] + 1;

                if (map[ny][nx] == 0) {
                    count++;
                    max = Math.max(max, dist[ny][nx]);
                }
                q.add(new int[]{ny, nx});
            }
        }

        if (emptyCount == count) {
            ans = Math.min(ans, max);
        }
    }
}