[java]연구소 3 - 백준17142

문제



풀이

문제 해석을 하자면,

  • 문제 조건에 맞춰서 바이러스가 “전부 장악한” 시점의 시간을 구하는 문제이며,
  • 이 시간의 최소시간을 구하는 문제이다.


풀이

  • 두가지로 나눠서 구현을 진행했다.
    • 먼저, “조합” 의 경우의 수로 접근 -> 따로 virusCount 로 바이러스 총 개수 구해서 사용 중요!!
    • 이후 BFS !! -> “빈값” 일때만 time 기록!!! (거리기록!!) 매우 중요 포인트
      • dist 배열로 거리를 측정해본적 있다면, 그 방식과 유사
      • 아래 두가지 반례를 해결하기 위한 목적도 있으니 참고
  • 그리고 구현의 편의를 위해서 아래 사항을 진행했다 -> 아래 최대값시간 도출 위해
    • 벽 1이 아닌 -1로 따로 표시
    • 바이러스도 2가 아닌 -2로 따로 표시
  • 마지막으로 전체 바이러스 장악 성공여부 확인 + dist(copy)배열 시간 최대값(=최종완료시간) 도출

아래 두가지 반례

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

0

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

4



코드

public static int N, M;
public static int virusCount;
public static int result=Integer.MAX_VALUE;
public static int[][] inArr = new int[55][55];
public static boolean[][] visited = new boolean[55][55];
public static int[] outArr = new int[15];
public static Pair[] virus = new Pair[15];
public static int[] dx = {0,1,0,-1};
public static int[] dy = {1,0,-1,0};

public static void bfs() {
    //inArr 복제
    int[][] copy = new int[55][55]; // -> dist 역할과 동일
    //init
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            visited[i][j] = false;
            copy[i][j] = inArr[i][j];
        }
    }

    Queue<Pair> qu = new LinkedList<>();
    for(int i=0; i<M; i++) {
        qu.add(virus[outArr[i]]);
        visited[virus[outArr[i]].x][virus[outArr[i]].y]=true;
    }

    int time = 0;
    while(!qu.isEmpty()) {
        int sizeQ = qu.size();
        time++;
        for(int s=0; s<sizeQ; s++) {
            Pair p = qu.peek();
            qu.remove();
            for(int i=0; i<4; i++) {
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];
                if(nx<0||ny<0||nx>=N||ny>=N) continue;
                if(visited[nx][ny] || copy[nx][ny]==-1) continue;

                visited[nx][ny] = true; // 방문은 일단 표시
                if(copy[nx][ny]==-2) {
                    qu.add(new Pair(nx, ny));
                    continue;
                }else {
                    copy[nx][ny]=time; // "빈값" 일때만 time 기록!!! (거리기록!!) 매우 중요 포인트
                    qu.add(new Pair(nx, ny));					
                }
            }
        }
    }

    // 전체 바이러스 장악 성공여부 확인 + dist(copy)배열 시간 최대값(=최종완료시간) 도출
    boolean fail = false; 
    int max = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(copy[i][j]==0) fail=true;
            if(max<copy[i][j]) max = copy[i][j]; // 최대값이 전부 바이러스 전파 완료한 시간
        }
    }
    if(!fail) result = Math.min(result, max);

    //debug
    //		for(int i=0; i<N; i++) System.out.println(Arrays.toString(copy[i]));
    //		for(int i=0; i<M; i++) System.out.print(outArr[i]+" ");
    //		System.out.println("virus 사용");
}

public static void dfs(int depth, int idx) {
    //base condition
    if(depth == M) {
        bfs();
        return;
    }
    //recursion
    for(int i=idx; i<virusCount; i++) {
        outArr[depth] = i; // virus의 index를 기록
        dfs(depth+1, i+1);
    }
}

public static void main(String[] args) throws Exception {
    //init
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    virusCount = 0;
    for(int i=0; i<N; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<N; j++) {
            inArr[i][j] = Integer.parseInt(stk.nextToken());
            if(inArr[i][j]==1) inArr[i][j]=-1; // 벽 -1로 따로 표시하겠음
            if(inArr[i][j] == 2) {
                virus[virusCount++] = new Pair(i,j);
                inArr[i][j] = -2; // 바이러스도 보기편하게 -2로 변경
            }
        }
    }
    //run
    //debug
    //		for(int i=0; i<N; i++) System.out.println(Arrays.toString(inArr[i]));
    //		System.out.println("시작전");

    dfs(0, 0);

    //output
    if(result == Integer.MAX_VALUE) result = -1; // 바이러스 장악 실패시 -1
    System.out.println(result);
}

static class Pair{
    int x; int y;
    public Pair(int x, int y) {
        this.x = x; this.y = y;
    }
}



느낀점

“빈값” 일때만 time(거리)을 기록 했으면 수많은 반례를 해결할 수 있었는데, 이를 너무 늦게 알았던 문제

댓글남기기

참고