[Beakjoon] 백준 28354_링크 컷 토마토 (Java)

28354번: 링크 컷 토마토

 

문제 풀이

내 첫 플래티넘 문제였다. 알고리즘은 제대로 구성해서 작성한 것 같은데, 계속 시간 초과가 나서 애먹었던 기억이 있다. 시간을 단축시키고자 BFS 방문 시 필요 없는 방문이 발생하지 않도록 조건도 체크했는데 시간 초과가 나서 며칠 동안 붙잡고 있었다. 

 

결론적으로 탐색이 더 효율적인 자료구조로 변경하니 통과되었다. 처음엔 그래프를 ArrayList로 구현했었는데, 그래프 안에 특정 정점이 존재하는 지 탐색할 때 O(N)의 시간이 소요되어 시간초과가 났다. 따라서 그래프를 HashSet으로 변경했다. HashSet은 해시 테이블을 기반으로 구현되어 있기 때문에 검색 요소의 해시 코드를 사용해 해당 요소에 바로 접근할 수 있으므로 O(1)의 시간 복잡도를 가진다.

 

알고리즘이 아닌 자료구조의 특성을 고려해 시간을 단축시킨 문제는 처음이라 신기했고 자료구조에 대한 학습의 필요성도 느낄 수 있었던 것 같다. 이런 이슈뿐만 아니라 edge의 유효 시간에 따라 특정 노드까지의 거리도 고려해야 하고 꽤나 까다로웠던 문제다. 

 

소스코드

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

public class Main {
    static HashSet<Integer>[] graph;
    static Queue<Change> change =new LinkedList<>();
    static Queue<Tomato> q = new LinkedList<>();
    static int[] days;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] NMKQ = br.readLine().split(" ");
        N = Integer.parseInt(NMKQ[0]);  // 토마토
        int M = Integer.parseInt(NMKQ[1]);  // 연결 쌍
        int K = Integer.parseInt(NMKQ[2]);  // 익은 토마토
        int Q = Integer.parseInt(NMKQ[3]);  // 상태변화 수

        graph = new HashSet[N+1];
        days = new int[N+1];
        for(int i = 1 ; i <= N ; i++){
            graph[i] = new HashSet<>();
            days[i] = -1;
        }

        for(int i = 0 ; i < M ; i++){
            String[] AB = br.readLine().split(" ");
            int A = Integer.parseInt(AB[0]);
            int B = Integer.parseInt(AB[1]);

            graph[A].add(B);
            graph[B].add(A);
        }

        // 익은 토마토 표시 및 큐에 넣기
        String[] ik = br.readLine().split(" ");
        for(String t: ik){
            int tomato = Integer.parseInt(t);
            days[tomato] = 0;
            q.add(new Tomato(tomato, 0));
        }


        // 연결 상태 변화 정보
        for(int i = 0; i < Q ; i++){
            String[] TXY = br.readLine().split(" ");
            int T = Integer.parseInt(TXY[0]);
            int X = Integer.parseInt(TXY[1]);
            int Y = Integer.parseInt(TXY[2]);
            change.add(new Change(T, X, Y));
        }

        int now = 0;
        while(!q.isEmpty()){
            Tomato poll = q.poll();
            if(poll.time > now){
                now = poll.time;
                updateGraph(now);
            }

            for(int next: graph[poll.num]){
                if(days[next] == -1){
                    days[next] = poll.time + 1;
                    q.add(new Tomato(next, poll.time+1));
                }
            }

            if(q.isEmpty()){
                while(!change.isEmpty() && q.isEmpty()){
                    updateGraph(change.peek().day);
                }
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 1 ; i <= N ; i++){
            bw.write(days[i]+" ");
        }
        bw.flush();   //남아있는 데이터를 모두 출력시킴
        bw.close();   //스트림을 닫음
    }

    private static void updateGraph(int day) {
       HashSet<Integer> check = new HashSet<>();
        while(true){
            if(!change.isEmpty() && change.peek().day == day){
                Change poll = change.poll();
                Integer a = poll.a;
                Integer b = poll.b;

				//연결 해제
                if(graph[a].contains(b) || graph[b].contains(a)){   
                    graph[a].remove(b);
                    graph[b].remove(a);
                }
                
                // 연결
                else{      
                    if(days[a] != -1 && days[b] == -1){
                        check.add(b);
                        q.add(new Tomato(b, day+1));
                    }else if(days[b] != -1 && days[a] == -1){
                        check.add(a);
                        q.add(new Tomato(a, day+1));
                    }
                    graph[a].add(b);
                    graph[b].add(a);
                }
            }else{
                break;
            }
        }

        for(int n : check){
            days[n] = day + 1;
        }
    }


    static class Tomato{
        int num;
        int time;

        Tomato(int n, int t){
            this.num = n;
            this.time = t;
        }
    }

    static class Change{
        int day;
        int a;
        int b;

        Change(int d, int a, int b){
            this.day = d;
            this.a = a;
            this.b = b;
        }
    }
}