[이코테][Java] 경쟁적 전염

[문제링크]

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

---

문제 설명

하나의 칸의 크기가 1 ×1인 N × N 크기의 시험관 안에 바이러스가 존재할 수 있고, 모든 바이러스는 1 ~ k번까지의 바이러스 종류 중 하나이다.

- 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식한다.

- 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다.

- 이미 어떠한 바이러스가 존재한다면 그곳에는 다른 바이러스가 들어갈 수 없다.

S초가 지난 후에 (X, Y)에 존재하는 바이러스의 종류를 출력하세요. 만약 해당 위치에 바이러스가 존재하지 않는다면 0 출력

 

입력조건

• 첫째 줄에 시험관의 크기 N, 바이러스 종류의 개수 K
• 둘째줄 ~ N+1번째 줄 까지 시험관 안에 바이러스 정보
• N+2번째 줄에 S, X, Y

출력조건

• S초 후에 (X, Y)에 존재하는 바이러스의 종류 출력

입출력 예시

입력예시	출력예시
3 3 1 0 2 0 0 0 3 0 0 2 3 2	3
3 3 1 0 2 0 0 0 3 0 0 1 2 2	2

 

 

 

 

문제 풀이

• BFS 알고리즘 사용
• Node 클래스를 생성해서 바이러스에 대한 정보를 저장하고, 이것을 리스트에 담는다.
• 번호가 낮은 바이러스 순을 바이러스가 증식하기 때문에, 바이러스 번호를 기준으로 오름차순 정렬
• 정렬한 바이러스 모두를 queue에 넣고 BFS 알고리즘 수행
  • queue에서 하나씩 꺼내서 상, 하, 좌, 우 탐색하면서 바이러스가 증식할 수 있는지 확인
  • 증식할 수 있으면 바이러스의 좌표위치 변경, 시간 증가해서 queue에 삽입
  • 시간이 s초가 됐을 때, BFS를 종료하고 (X, Y)에 존재하는 바이러스의 번호 출력

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

public class Main {
    static class Node {
        int x;  //바이러스 위치의 행
        int y;  //바이러스 위치의 열
        int virus;  //바이러스 종류
        int time;   //바이러스가 몇 초에 증식되었는지를 나타내는 시간

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

    public static int n, k, s;
    public static int[][] map;
    public static Queue<Node> q = new LinkedList<>();

    public static void bfs() {

        //상, 하, 좌, 우
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

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

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

            //상, 하, 좌, 우로 움직이면서 바이러스가 증식할 수 있는지 확인
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                //시험관 영역을 벗어나면 무시
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
                    continue;
                }
                //해당 칸이 비어있으면 바이러스가 증식 가능
                if (map[nx][ny] == 0) {
                    map[nx][ny] = cur.virus;
                    q.offer(new Node(nx, ny, cur.virus, cur.time + 1));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());   //s초
        int x = Integer.parseInt(st.nextToken());   //s초 후 바이러스의 행 위치
        int y = Integer.parseInt(st.nextToken());   //s초 후 바이러스의 열 위치

        bfs();

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

 

✔️ 문제를 읽고 하나의 바이러스 증식을 구현하기 위해서 BFS 알고리즘을 사용해야겠다고 생각했다.

또한 바이러스 번호가 낮은 순으로 증식하기 때문에 바이러스를 오름차순 정렬해야함도 알고 있었다.

하지만 동시에 여러 개의 바이러스를 증식하는 방법을 생각해내는데 어려움을 겪었다. DFS/BFS 문제를 많이 풀어봐야겠다.

---

 

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈