[백준 18405] - 경쟁적 전염(JAVA)

[문제] 

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

18405번: 경쟁적 전염

---

 

 

[문제풀이 전] 

이코테 책뒤에 DFS&BFS 17번 문제로 나온 문제이기도 하다. 백준에서 정답률 28%로 낮은 정답률을 보유하고 있는데 요즘 스터디의 효과를 보는지 한번에 통과해서 기분이 좋았다. 아마 이 문제에서 접근하기 어려운점이 모든 바이러스는 1초마다 상, 하, 좌. 우 방향으로 증식하는데 바이러스는 매 초마다 낮은 종류의 바이러스가 증식하고 그 시점에 증식할 곳에 바이러스가 있으면 증식을 할 수 없다를 처리 하기가 까다로웠다고 생각을 합니다.

왜냐하면 바이러스는 낮은 순서부터 동시(매초)에 증식해야하는데 이 동시에 대한 처리가 프로그램에서 구현하기 까다롭기 때문입니다.

 

 

---

 

 

[문제풀이] 

매초마다 모든 바이러스가 증식을 해야합니다 그래서 좌표값과 바이러스의 종류, 시간 값을 가지는 노드 클래스를 따로 만들었습니다. 그 후 맵에있는 모든 바이러스를 리스트에 추가를 해줍니다. 리스트에 담겨있는 노드들을 바이러스가 오름차순이 되도록 정렬 해줍니다. 정렬해준 리스트들을 모두 큐에 넣고 BFS를 사용하여 증식이 될 때 마다 시간을 증가시킵니다. 이렇게 되면 모든 바이러스가 낮은 종류부터 동시에 처리하는 결과를 냅니다. S초가되면 종료를 하고 문제에서 요구하는 바이러스의 종류를 출력하면 됩니다.

 

 

정리하면

• 좌표값, 바이러스 종류, 시간 값을 가지는 노드 클래스 만들기
• 맵에있는 바이러스 리스트에 담기
• 리스트에 있는 바이러스 정렬( Comparator 사용 -  바이러스 오름차순) 
• 리스트에 있는 바이러스 큐에 넣고 BFS 시작
• 탐색이 될 경우 시간 증가
• 문제에서 요구하는 S초가 됐을 경우 종료하고 답 출력 

 

 

---

 

 

[소스코드] 

 

 

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

public class Main {

    static class Node{
        int x;
        int y;
        int virus;
        int time;

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

    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {1, -1, 0, 0};
    static int n, k, s;
    static int[][] map;
    static Queue<Node> q = new LinkedList<>();

    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];
        ArrayList<Node> 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 Node(i, j, map[i][j], 0));
                }
            }
        }

        Collections.sort(list, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.virus - o2.virus;
            }
        });

        for (Node node : list) {
            q.add(node);
        }

        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

        bfs();

        System.out.println(map[x - 1][y - 1]);
    }

    static void bfs() {

        while (!q.isEmpty()) {
            Node now = q.poll();
            int x = now.x;
            int y = now.y;

            if (now.time == s) {
                return;
            }

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

                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (map[nx][ny] == 0) {
                        map[nx][ny] = now.virus;
                        q.add(new Node(nx, ny, now.virus, now.time + 1));
                    }
                }
            }

        }

    }
}

 

 

 

 

 

언제든 지적 or 궁금한 점 댓글로 남겨주시면 빠르게 답변 드리겠습니다. 감사합니다.