[BOJ] 17142 연구소 3 - Java

부들부들

1. 문제 링크

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

17142번: 연구소 3

---

2. 문제 풀이

아니, 알고리즘 문제는 어차피 자기 자신이 풀어야 하는 거라서 사용되는 알고리즘 외에는 따로 해설은 필요 없다고 생각했습니다만. 어제오늘 너무 반례 때문에 화가 나서 도저히 안 되겠습니다. 이 문제는 좀 많이 혼나야 해요. 오죽하면 제가 평소에는 쓰지도 않던 반례 공유 게시글을 쓰겠냐구요. 내 삽질이 내 코드보다 가취치 있기를 ,,🤡 

https://www.acmicpc.net/board/view/112928

글 읽기 - <<저를 구원해 준 반례들을 공유합니다.>>

예전에는 큐에 배열을 그대로 넣어서 문제를 풀었지만, 요새는 노드 클래스를 만들어서 보기 좋게 큐를 다루고 있습니다.
bfs와 조합으로 문제를 풀었는데, 반례 때문에 생각보다 많이 애를 먹었습니다. 이젠 bfs 고수가 되었다고 생각했는데 아직 한참 멀었네요.
삼성 가고 싶다.

문제를 푸는 데 사용한 변수와 메소드는 아래와 같습니다.

• bfs를 돌릴 큐
• 방문 체크용 boolean형 visited 배열
• 전체 map 배열
• 초기 map의 상태를 저장하는 copy map 배열
• 바이러스를 놓을 수 있는 위치를 저장하는 리스트
• 조합으로 만들어진 바이러스를 체크하는 boolean형 배열
• 조합 : com()
• bfs()
• map의 바이러스 상태를 체크하고 최소 시간을 구하는 check()

큐에 바이러스 위치를 넣고 bfs를 돌려주면 끝날 줄 알았는데 문제를 제대로 읽어야 합니다.

문제의 녀석..

활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변하는데, 이것을 염두에 두고 문제를 풀어야 합니다.

그리고 하단에 첨부한 Input 7에 있는 테스트 케이스의 경우 0초가 걸리게 되는데 어디에 바이러스를 활성화시키든 이미 map에는 전부 바이러스가 활성화되어서 그렇습니다.

5 1
2 2 2 1 1
2 1 1 1 1
2 1 1 1 1
2 1 1 1 1
2 2 2 1 1

또 또 또 또

그리고 Input 1의 테스트 케이스에서 비활성 바이러스가 활성화되었을 텐데 시간은 5초로 카운트되지 않았죠? 이것도 유념하셔야 합니다. 저는 여기서 헤맨 것은 아니지만 혹시라도 문제 풀이 힌트가 필요한 사람을 위해서 적었음.
비활성 바이러스를 만났을 때 얘를 밟고 지나갈지(시간을 ++할지) 아니면 그냥 내버려 둘지를 생각하면서 문제를 풀었습니다.

 

좋은 소스코드는 주석이 없어도 잘 읽히는 소스코드라고 봤는데 과연 제 소스 코드가 자기소개를 제대로 하고 있는 건지는 잘 모르겠습니다만.. 따로 주석은 적지 않겠습니다. 함수로 분리해 놓은 것만으로도 감사하십쇼. (감사합니다. Madirony님님님님님님)

티스토리 코드 블럭은 자바 소스 코드를 그냥 찢어버리네요. 제 블로그는 복사가 금지되어 있지만 코드 블럭 안의 소스 코드는 복사가 가능하도록 스킨을 바꿔 놨는데 왜 강제 라인 랩핑을 ... 😡

앞으로 자바 코드는 보기 편하게 GIST로 달아놓을 테니 소스코드가 필요하다면 소스코드 하단에 있는 GIST 링크로 가면 됩니다. 얘는 코드블럭 취급이 안 돼서 블로그 내에서는 복사가 안 되는 것 같네요. @.@

 

2023.03.21  이제 테마도 좀 이쁘게 꾸미고 코드 보기 편하게 가로 스크롤까지 달아놨음 ^-^

---

3. 소스 코드

import java.io.*;
import java.util.*;
public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int[][] arr;
    static int[][] copy;
    static int n, m, min = Integer.MAX_VALUE;
    static Queue<Node> queue = new LinkedList<>();
    static boolean[][] visited;
    static List<Node> putArr = new ArrayList<>();
    static boolean[] virus;
    static class Node{
        int x;
        int y;
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    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());
        arr = new int[n][n]; visited = new boolean[n][n]; copy = new int[n][n];
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 1)
                    arr[i][j] = -1;
                else if(arr[i][j] == 2)
                    putArr.add(new Node(i, j));
            }
        }
        virus = new boolean[putArr.size()];
        for(int i = 0; i < arr.length; i++)
            System.arraycopy(arr[i], 0, copy[i], 0, arr[0].length);
        com(0, 0);
        if(min == Integer.MAX_VALUE)
            min = -1;
        System.out.println(min);
    }
    static void com(int start, int cnt){
        if(cnt == m){
            bfs();
            return;
        }
        for(int i = start; i < putArr.size(); i++){
            if(!virus[i]){
                virus[i] = true;
                com(i + 1, cnt + 1);
                virus[i] = false;
            }
        }
    }
    static void bfs(){
        for(int i = 0; i < putArr.size(); i++){
            if(virus[i]){
                visited[putArr.get(i).x][putArr.get(i).y] = true;
                arr[putArr.get(i).x][putArr.get(i).y] = 0;
                queue.add(putArr.get(i));
            }
        }
        while(!queue.isEmpty()){
            Node tmp = queue.poll();
            for(int i = 0; i < 4; i++){
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if(0 <= nx && nx < n && 0 <= ny && ny < n){
                    if(!visited[nx][ny]){
                        switch(arr[nx][ny]){
                            case 0:
                                queue.add(new Node(nx, ny));
                                visited[nx][ny] = true;
                                arr[nx][ny] = arr[tmp.x][tmp.y] + 1;
                                break;
                            case -1:
                                visited[nx][ny] = true;
                                break;
                            case 2:
                                for(int j = 0; j < 4; j++){
                                    int tmpx = nx + dx[j];
                                    int tmpy = ny + dy[j];
                                    if(0 <= tmpx && tmpx < n && 0 <= tmpy && tmpy < n){
                                        if(!visited[tmpx][tmpy] && arr[tmpx][tmpy] == 0 || arr[tmpx][tmpy] == 2) {
                                            queue.add(new Node(nx, ny));
                                            arr[nx][ny] = arr[tmp.x][tmp.y] + 1;
                                        }
                                    }
                                }
                                break;
                        }
                    }
                }
            }
        }
        check();
        for(int i = 0; i < copy.length; i++)
            System.arraycopy(copy[i], 0, arr[i], 0, copy[0].length);
        visited = new boolean[n][n];
    }
    static void check(){
        int cnt = 0, virus = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(arr[i][j] == 0)
                    virus++;
                if(visited[i][j])
                    cnt = Math.max(cnt, arr[i][j]);
            }
        }
        if(m < virus)
            return;
        min = Math.min(min, cnt);
    }
}

3-1. 반례

11 2
1 1 0 1 1 1 1 1 0 1 1
1 1 2 1 1 1 1 1 2 1 1
0 1 2 1 1 1 0 1 2 1 1
0 1 0 1 1 1 0 1 0 1 1
0 0 2 0 0 1 0 0 2 0 0
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
answer : 4
    
    
9 1
0 2 2 2 2 2 2 2 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
answer : 4
    
    
5 1
2 2 2 1 1
2 1 1 1 1
2 1 1 1 1
2 1 1 1 1
2 2 2 1 1
ex 7) answer : 0

    
5 2
2 2 2 1 1
2 1 1 1 1
2 1 1 1 2
2 1 1 1 1
2 2 2 1 1
answer : 0
    
    
5 2
2 2 2 1 1
2 1 1 1 0
2 1 1 1 2
2 1 1 1 1
2 2 2 1 1
answer : 1

    
5 2
2 2 2 1 1
2 1 1 1 0
2 1 1 1 2
2 1 1 1 0
2 1 1 1 0
answer : 2
    
    
5 2
0 1 1 1 0
2 1 1 1 2
2 1 1 1 2
2 1 1 1 2
0 1 1 1 0
answer : 2

---

4. 한줄평

시간 재고 풀기. 문제 꼼꼼히 읽기.