[JAVA] 백준 - 17142 : 연구소 3

문제 링크

17142번: 연구소 3

 

 

풀이 )

  처음에는 방문 여부를 나타내는 boolean 2차원 배열 visited를 선언하지 않고 풀려다가 많은 문제가 발생했다.

• 비활성화된 바이러스를 0으로 갱신하고 시작
  • 처음에 다 퍼져있는 경우에 대해서 다른 결과를 출력한다.
• 바이러스가 방문한 곳을 2로 갱신하고, 1이 아닌 곳만 방문
  
  • 큐에 중복 방문으로 인한 메모리 초과
• 바이러스가 방문한 곳을 3으로 갱신하고, 0 2인 곳만 방문
  
  • 비활성화된 바이러스를 벽으로 생각함

 

  결국 visited 배열을 사용해서 했다.

 

  자세한 풀이는 아래 주석을 달아두었다.

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

public class Main {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static int n,m;
    static int[][] board;
    static int ans = (int)1e7;
    static ArrayList<Point> virusList = new ArrayList<>();

    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());
        board = new int[n][n];
        for(int i = 0; i < n; ++i){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < n; ++j){
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j] == 2){
                    virusList.add(new Point(i, j));
                }
            }
        }
        // 입력 & 비활성화된 바이러스를 list에 저장

        combination(m, new int[m], 0);	// 활성화될 바이러스 선택(조합 - virusList.size() C m)
        if(ans == (int)1e7)
            ans = -1;
        System.out.println(ans);
    }

    static void combination(int toPick, int[] picked, int pos){
        if(toPick == 0){
            bfs(picked);	// 활성화될 바이러스를 시작으로 bfs 탐색
            return;
        }

        for(int i = pos; i < virusList.size(); ++i){
            picked[picked.length-toPick] = i;
            combination(toPick-1, picked, i+1);
        }
    }

    static void bfs(int[] picked){
        int[][] tmp = new int[n][];
        for(int i = 0; i < n; ++i)
            tmp[i] = board[i].clone();	// board 값에 영향을 주지 않기 위한 임시 배열
        boolean[][] visited = new boolean[n][n];	// 방문 여부

        Queue<Point> virusQ = new LinkedList<>();
        for(int i = 0; i < picked.length; ++i){
            Point virus = virusList.get(picked[i]);
            virusQ.offer(virus);
            visited[virus.x][virus.y] = true;
        }	// 활성화될 바이러스를 큐에 집어 넣으면서 방문여부 갱신

        int time = -1;	// 바이러스가 퍼지는데 걸리는 시간
        while(!virusQ.isEmpty()){
            time++;
            boolean flag = false;	// 바이러스가 퍼졌는지 확인할 때 2중 for문을 탈출하기 위한 flag
            for(int i = 0; i < n; ++i){
                for(int j = 0; j < n; ++j)
                    if(tmp[i][j] == 0){
                        flag = true;
                        break;
                    }
                if(flag)
                    break;
            }
            if(!flag){	// 바이러스가 더이상 퍼질 수 없으면 ans를 갱신하고 종료
                ans = Math.min(ans, time);
                return;
            }

            int size = virusQ.size();
            while(size-- > 0){
                Point cur = virusQ.poll();
                int x = cur.x, y = cur.y;
                for(int dir = 0; dir < 4; ++dir){
                    int nx = x+dx[dir], ny = y+dy[dir];
                    if(!isIn(nx, ny) || tmp[nx][ny] == 1 || visited[nx][ny])	// 확산할 수 없는 경우
                        continue;
                    visited[nx][ny] = true;	// 확산할 수 있는 경우 방문 여부와 임시 배열을 갱신하고, 큐에 추가
                    tmp[nx][ny] = 2;
                    virusQ.offer(new Point(nx, ny));
                }
            }
            if(virusQ.isEmpty())
                break;
        }
    }

    static boolean isIn(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < n;
    }
}

 

주의 )

  처음 ans의 값을 100으로 설정해서 틀렸다.

  초기에 주어진 바이러스가 1개이고 가로세로 50의 ㄹ모양의 연구소가 주어지면 100초 이상 걸리기 때문에 넉넉한 값을 주어야 한다.