[백준] 18405 경잭적 전염 - 자바

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

18405번: 경쟁적 전염

 

문제 풀이

이 문제는 시간복잡도를 신경써서 해결해야 한다. 문제 조건을 보면 알겠지만 단순 하나하나 값들은 작지만 서로 영향을 주기 때문에 반복죽으로 일어난다. 따라서 N X N에 대해 K개의 바이러스를 찾아 전파하는 로직으로는 1초 제한시간 안에 해결할 수 없을 것이다.

따라서 값을 받아올 때 바이러스에 대한 좌표(x,y), 종류(k), 증식시간 에 대한 정보를 저장하고 종류 즉 k값을 정렬시켜 작은 값부터 전파를 이어나갈 것이다.

 

코드

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

class Virus {

    private int index;
    private int second;
    private int x;
    private int y;

    public Virus(int index, int second, int x, int y) {
        this.index = index;
        this.second = second;
        this.x = x;
        this.y = y;
    }

    public int getIndex() {
        return this.index;
    }

    public int getSecond() {
        return this.second;
    }

    public int getX() {
        return this.x;
    }

    public int getY() {
        return this.y;
    }

}

public class b18405 {

    public static int n, k;
    // 전체 보드 정보를 담는 배열
    public static int[][] graph = new int[200][200];
    public static ArrayList<Virus> viruses = new ArrayList<>();

    // 바이러스가 퍼져나갈 수 있는 4가지의 위치
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        k = sc.nextInt();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = sc.nextInt();
                // 해당 위치에 바이러스가 존재하는 경우
                if (graph[i][j] != 0) {
                    // (바이러스 종류, 시간, 위치 X, 위치 Y) 삽입
                    viruses.add(new Virus(graph[i][j], 0, i, j));
                }
            }
        }

        // 정렬 이후에 큐로 옮기기 (낮은 번호의 바이러스가 먼저 증식하므로)
        Collections.sort(viruses, Comparator.comparingInt(Virus::getIndex));

        // 값이 낮은 순서대로 q에 삽입
        Queue<Virus> q = new LinkedList<>();
        for (int i = 0; i < viruses.size(); i++) {
            q.offer(viruses.get(i));
        }

        int targetSec = sc.nextInt();
        int targetX = sc.nextInt();
        int targetY = sc.nextInt();

        // 너비 우선 탐색(BFS) 진행
        while (!q.isEmpty()) {
            Virus virus = q.poll();
            // 정확히 second만큼 초가 지나거나, 큐가 빌 때까지 반복
            if (virus.getSecond() == targetSec) break;
            // 현재 노드에서 주변 4가지 위치를 각각 확인
            for (int i = 0; i < 4; i++) {
                int nx = virus.getX() + dx[i];
                int ny = virus.getY() + dy[i];
                // 해당 위치로 이동할 수 있는 경우
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    // 아직 방문하지 않은 위치라면, 그 위치에 바이러스 넣기
                    if (graph[nx][ny] == 0) {
                        graph[nx][ny] = virus.getIndex();
                        q.offer(new Virus(virus.getIndex(), virus.getSecond() + 1, nx, ny));
                    }
                }
            }
        }

        System.out.println(graph[targetX - 1][targetY - 1]);
    }
}

 

느낀점

bfs dfs문제는 한 번 감 잡으면 나름 수월하게 진행되나 싶다가도 자주 막히는 문제인 것 같다. 더 많은 문제를 풀어봐야겠다