18405 - 경쟁적 전염 (Java)

 

---

 

문제

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

 

풀이

아주 조금의 응용이 들어간 bfs 문제였다.

 

우선 바이러스가 존재하는 위치를 queue에 저장했다.

 

단, 바이러스가 여러종류가 있기 때문에 map 을 활용해서 key로 바이러스 번호를 설정하고 그 값으로 해당 바이러스 위치를 가지고 있는 queue 를 꺼내올 수 있도록 설정했다.

 

이후에는 bfs 를 수행하는데, 이 때 전염이 1회 된다는 점을 주의해야한다.

 

가장 최근에 전염된 바이러스만 자신 주변으로 감염을 시키기 때문에 queue에는 최근 전염된 바이러스들의 위치만 존재해야하고, 다음에 queue를 넣을때도 마찬가지여야 한다.

 

숫자가 낮은 바이러스부터 전염되기 때문에 작은 숫자의 바이러스의 queue 부터 접근했고,

해당 queue의 위치를 우선 모두 꺼낸다음에 list에 넣었다.

이후 조건에 따라 전염될 수 있는 곳이라면 전염을 시키고 그 위치를 새로운 queue 에 저장시켰다.

 

이렇게 반복후에, 새롭게 전염된 위치만 존재하는 queue 를 해당 바이러스의 queue로 바꿔주었다.

 

코드

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

public class Main {

    public static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

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

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        Map<Integer, ArrayDeque<Node>> map = new HashMap<>();
        for(int i=1; i<=k; i++) map.put(i, new ArrayDeque<>());

        // Initialize
        int[][] board = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for(int j=0; j<n; j++) {
                int keyVal = Integer.parseInt(line[j]);
                board[i][j] = keyVal;
                if(keyVal != 0 ) {
                    map.get(Integer.parseInt(line[j])).addLast(new Node(i, j));
                }
            }
        }

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

        int s = Integer.parseInt(st.nextToken());
        int rx = Integer.parseInt(st.nextToken());
        int ry = Integer.parseInt(st.nextToken());


        // 처음 이후, 퍼진 값들의 위치를 어떻게 기억할것인가?
        // 1번부터 k번까지 각각의 queue 를 가지고 있고, 돌면서 사용한다.

        // k초 동안 전염을 수행한다.
        while(s != 0){

            for (int i = 1; i <= k; i++) {
                // i 번 바이러스부터 전염 수행한다.
                ArrayDeque<Node> queue = map.get(i);
                ArrayDeque<Node> newQueue = new ArrayDeque<>();

                while(!queue.isEmpty()){
                    Node node = queue.removeFirst();
                    int x = node.x;
                    int y = node.y;

                    // 4방향을 검사한다.
                    for(int j=0; j<4; j++){
                        int nx = x + dx[j];
                        int ny = y + dy[j];

                        if(nx>= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 0){
                            board[nx][ny] = i; // 바이러스 전염
                            newQueue.addLast(new Node(nx, ny));
                        }
                    }
                }

                // 새로운 queue 로 바꿔준다.
                map.put(i, newQueue);
            }
            s--;
        }

        System.out.println(board[rx-1][ry-1]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }


}

 

후기