[백준] 18405번 경쟁적 전염

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

18405번: 경쟁적 전염

---

문제에서 바이러스는 시간에 따라 번식하게 되는데, 바이러스의 번식은 한 번에 모든 바이러스가 동시에 일어나는 것이 아니라 순차적으로 진행된다. 따라서 이러한 상황을 시뮬레이션하기 위해 큐를 사용한다.

 

큐를 사용하는 이유:

1. 순차적 처리: 바이러스가 번식하는 것은 순차적으로 진행된다. 큐를 사용하면 선입선출(FIFO)의 특성을 이용하여 먼저 들어온 바이러스부터 순서대로 번식시킬 수 있다.
2. 다음 단계 예약: 바이러스가 번식하는 동안에도 다음에 번식할 바이러스들을 큐에 추가하여 다음 단계의 번식을 준비할 수 있다.

=> 해당 문제는 큐, 즉 BFS를 활용하여 풀었다. 

 

처음에는 바이러스가 K개의 종류가 있고 각자 다른 좌표에서 번식하기 때문에(= 시작점이 하나가 아니다) 큐를 k개만큼 생성하고, 노드 방문 표시를 하게 해서 문제를 해결하려고 했으나,,, 갈수록 복잡해지고 무려 3중 for문이 생겨버려서 pass

 

두 번째 시도로는 Virus 객체를 만들고 우선순위 큐를 통해 바이러스 번호가 작은 것부터 poll() 할 수 있도록 했는데, 예제는 통과하지만 제출하면 실패했다. 각 S마다 순서대로 poll()을 진행하도록 했어야 했는데, 그냥 우선순위 큐에 다 넣다보니 S에 상관없이 poll 되어 생긴 문제였다. ( = 우선순위 큐를 사용하다보니 S에 따라서 1,2,3 순서로 진행되어야하는데 type이 1인 것이 자꾸 q의 앞에 담겨서, 1번 바이러스만 번식하고 있음)

 

** 틀린 코드.. 

package yejin.song;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_경쟁적전염 {

    static int map[][];
    static int N,K,S,X,Y;
    static boolean[][] visited;
    static int dx[] = {0,0,-1,1};
    static int dy[] = {1,-1,0,0};

    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());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        visited = new boolean[N][N];

        // 맵 초기화
        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());
            }
        }

        st = new StringTokenizer(br.readLine());

        S = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());

        bfs();
        System.out.println(map[X-1][Y-1]);
    }

    public static void bfs(){
        // 번호 작은 순서대로 처리하기 위한 우선순위 큐
        PriorityQueue<Virus> q = new PriorityQueue<>((v1, v2) -> v1.type - v2.type);
        //PriorityQueue<Virus> q = new PriorityQueue<>(Comparator.comparingInt(v -> v.type));


        // 초기 바이러스 정보 큐에 넣기 (= 맵에 0이 아닌 값 있으면 큐에 넣기)
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] != 0) {
                    q.offer(new Virus(map[i][j], i, j, 0));
                }
            }
        }

        // 큐를 이용한 BFS
        while (!q.isEmpty()) {
            Virus virus = q.poll();
            if (virus.time == S) break;

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

                // 좌표가 유효하다면 (0~N)
                if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                    if (map[nx][ny] == 0) {
                        map[nx][ny] = virus.type;
                        q.offer(new Virus(virus.type, nx, ny, virus.time + 1));
                    }
                }
            }
        }
    }

    static class Virus {
        int type, x, y, time;

        public Virus(int type, int x, int y, int time) {
            this.type = type;
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }
}

 

그래서, 처음에 맵 초기화하면서 맵에 0이 아닌 값 (= 바이러스)이 담길 때 list에 값을 추가하고 오름차순으로 정렬했다.

이 후에 큐에 담으면 순서대로 담기기 때문에 우선순위 큐를 사용하지 않더라도 해당 문제를 해결할 수 있다.

 

• Comparator : Comparator는 Java에서 객체들의 정렬 순서를 지정하는 데 사용되는 인터페이스
  • 해당 인터페이스를 람다식을 통해 list가 오름차순으로 정렬될 수 있도록 했다.
• Collections.sort(list, comparator) : 정렬
  • 위에서 만들어준 Comparator를 기준으로 정렬할 수 있도록 했다.  

package yejin.song;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_경쟁적전염 {
    static int map[][];
    static int N,K,S,X,Y;
    static boolean[][] visited;
    static int dx[] = {0,0,-1,1};
    static int dy[] = {1,-1,0,0};

    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());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        visited = new boolean[N][N];

        Queue<Virus> q = new LinkedList<>();

        Comparator<Virus> comparator = (v1, v2) -> v1.type - v2.type;
        ArrayList<Virus> list = 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] != 0) {
                    list.add(new Virus(map[i][j], i, j, 0));
                }
            }
        }
        Collections.sort(list, comparator);

        for (Virus virus : list){
            q.offer(virus);
        }

        st = new StringTokenizer(br.readLine());

        S = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());


        // S 시간까지 진행
        while (!q.isEmpty() && q.peek().time < S) {
            Virus virus = q.poll();
            if (virus.time == S) break;
            bfs(virus, q);
        }

        System.out.println(map[X-1][Y-1]);
    }

    public static void bfs(Virus virus, Queue<Virus> q){

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

            if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] == 0) {
                map[nx][ny] = virus.type;
                q.offer(new Virus(virus.type, nx, ny, virus.time + 1));
            }
        }
    }

    static class Virus {
        int type, x, y, time;

        public Virus(int type, int x, int y, int time) {
            this.type = type;
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }
}

 

 

++ 다시풀기 (성공)

import java.util.*;
import java.io.*;

public class codingTest {
    static int map[][];
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int S;
    static int N;
    static int K;



    public static void main(String[] args) throws IOException {
        // 일단 bfs -> 빙문했는지 확인하고, 큐에 넣고(int[]),...?
        // 이거는 각 초마다로 반복해야함. & 작은 수부터 시작한다 (정렬?)

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][N];

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

        st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken()); // 몇초 후?
        int X = Integer.parseInt(st.nextToken()); //확인할 X
        int Y = Integer.parseInt(st.nextToken()); //확인할 Y

        bfs();

        System.out.println(map[X-1][Y-1]);

    }

    public static void bfs(){ // S까지 됐거나 , q가 비었으면 종료

        Queue<Virus> q = new LinkedList<>();
        List<Virus> list = new ArrayList<>();

        // map 중에 0 아닌 수들 리스트에 담기
        for (int i = 0; i< N; i++){
            for (int j = 0; j < N; j++){
                if (map[i][j] !=0){
                    list.add(new Virus(map[i][j], 0,i,j));
                }
            }
        }

        // 리스트 순서 정렬하기 (초반 한번만 오름차순 정렬하면, 나머지는 알아서 차곡차곡 담긴다.)
        Collections.sort(list, (o1,o2) -> o1.type - o2.type);

        // 정렬된 순서대로 큐에 담기
        for (Virus virus: list){
            q.add(virus);
        }

        while (!q.isEmpty() && q.peek().s < S){
            // 큐 뽑고
            // 주변 탐색해서 방문X && 값이 0이면 -> map 업데이트(번호로 바꾸기) , 방문처리, 큐에 넣기(시간 +1)

            Virus virus = q.poll();
            int x = virus.x;
            int y = virus.y;


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

                if (searchX < 0 || searchY < 0 || searchX >= N || searchY >= N) continue;
                if (map[searchX][searchY] ==0){
                    map[searchX][searchY] = virus.type;
                    q.add(new Virus(virus.type, virus.s+1, searchX, searchY));
                }
            }
        }
    }

    static class Virus{
        int type, s, x ,y;

        public Virus(int type, int s, int x, int y){
            this.type = type;
            this.s = s;
            this.x = x;
            this.y = y;
        }
    }
}