백준 17142

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

17142번: 연구소 3

후........이거 정말 15번은 제출한 것 같다. 말이 15번이지 진짜 몇시간 내내 계속 붙들고 있었음. 계속 시간초과가 떠서 뭐가 문젠지 계속 살폈었는데 허무하게도 내가 조합 구하는 함수 재귀호출 하는 부분에서 변수를 잘못 넣었었다. 답은 제대로 나오지만 왜 시간초과가 났는지 모르겠어서 다른 분 코드보고 읽고 하다가 겨우 찾았다.... 내 코드에선 너무나 까막눈이 되는 것.. BFS쪽 잘못 짠 거 같아서 계속 여기만 디버깅하고 팠었는데 ㅋㅋㅋㅋㅋ 다른 부분이었다. 

 

---

💉 변수

- 방향용 배열인 dirX, dirY 

- 바이러스 위치 저장용 ArrayList<Pos> virus

- 활성화된 바이러스(조합에서 선택된) 위치용 ArrayList<Pos> selected;

- n : 연구소 크기, m : 활성화 시킬 바이러스 

- empty : 빈칸 크기, 채워진 칸 수가 얘랑 같아지면 탐색 끝내고 minTime 출력

- minTime : 최소 시간 갱신용, empty == 퍼뜨려진 칸 개수일 때 갱신한다. 처음엔 Integer.MAX_VALUE로 초기화할 것

- visited[][] 바이러스 조합 당 각 칸 당 퍼질 때까지 얼마나 시간 소요되는지 저장용 

public static int[] dirX = { 1, 0, -1, 0}; 
public static int[] dirY = {0, 1, 0, -1};
public static int[][] map;
public static ArrayList<Pos> virus;
public static ArrayList<Pos> selected;
public static int n, m, empty, minTime;

💉메인로직 

- 만약 빈칸 개수가 0이면 그냥 0출력하고 바로 끝낸다

- 가능한 바이러스 조합을 하나씩 구한다(백트래킹 - 재귀)

- 한 조합 당 spread()를 통해 다 퍼지는데 얼마나 걸리는지 확인한다. 

- 바이러스가 다 퍼졌다면 마지막 칸의 visit[][] 값과 minTime 값을 비교하여 갱신한다. 

- 만약 minTime이 Integer.MIN 아니면 고대로 출력. 아니면 -1 출력(어떤 방법을 써도 다채우지 못했다는 뜻이므로)

 

💉 코드

메인 함수

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());

        empty = 0;
        minTime = Integer.MAX_VALUE;
        map = new int[n][n];
        virus = new ArrayList<>();
        selected = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int value = Integer.parseInt(st.nextToken());
                if (value == 0) {
                    empty++;
                }
                else if (value == 2) {
                    virus.add(new Pos(i, j));
                }
                map[i][j] = value;
            }
        }

        if (empty == 0) {
            System.out.println(0);
        } else {
            combination(0,0);
            System.out.println(minTime == Integer.MAX_VALUE ? -1 : minTime);
        }


    }

 

가능한 바이러스 위치 조합을 구하기( combination()  )

public static void combination(int cur, int count) {
        if (count == m) {
            spread();
            return;
        }
        for (int i = cur; i < virus.size(); i++) {
            selected.add(virus.get(i));
            combination(i+1, count + 1); // 이걸 cur+1로 넣어서 시간초과가 났었다.. 
            selected.remove(virus.get(i));
        }
}

BFS 방식으로 해당 칸 기준 4방향을 탐색하며 퍼뜨리기 (spread)

💉💉💉 중요 ! 

- visited[nextX][nextY] = 0인 경우 2가지를 생각해야 한다. 

- 진짜 빈칸인 경우 -> count를 증가 (퍼트린 칸수)

- 비활성화된 바이러스인 경우 -> count 증가시키면 안됨!!! 

public static void spread () {
        Queue<Pos> queue = new LinkedList<>();
        int[][] visited = new int[n][n];
        // 먼저 큐에 바이러스의 위치들을 기록한다. 방문했다는 뜻에서 1로 초기화  
        for (int i = 0; i < selected.size(); i++) {
            queue.add(selected.get(i));
            visited[selected.get(i).x][selected.get(i).y] = 1;
        }
        int count = 0;
        while (!queue.isEmpty()) {
            Pos pos = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = pos.x + dirX[i];
                int nextY = pos.y + dirY[i];
                Pos next = new Pos(nextX, nextY);
                if (!isValid(next) || map[nextX][nextY] == 1 || visited[nextX][nextY] != 0) {
                    continue;
                }
                
                if (visited[nextX][nextY] == 0) {
                    if (map[nextX][nextY] == 0) {
                        count++; // 빈칸인 경우만 count 증가!! 
                    }
                    visited[nextX][nextY] = visited[pos.x][pos.y] + 1;
                    queue.add(next);
                    if (count == empty) {
                        minTime = Math.min(minTime, visited[nextX][nextY] - 1);
                    }
                }
            }
        }
}