문제 바로가기

나의 풀이

input으로 주어지는 노드들 사이에 빈칸이 주어져서 StringTokenizer를 사용하였다. 다만 BufferedReader를 사용해 readLine()을 쓸만큼 각 문장이 길지는 않아서 효율적인가에 대해서는 한번 생각해봐야 할 것 같다.

다만 Scanner 보다는 무조건 빠를 것이라고 생각한다. Scanner.nextInt()를 쓰면 nextInt() 메소드에서 오버로딩된 nextInt(int radix) 메소드로 보내지고, 내부 try-catch문에 존재하는 String s = next(integerPattern());의 integerPattern()을 통해 buildIntegerPatternString()을 호출한다.
더 자세한 내용은 이 블로그에 가도록 하자

여기서 필요 이상의 많은 정규식을 검사하므로 Scanner는 느리다는 것이다.

이어 System.out.println() 또한 BufferedWriter를 사용하는 것에 비해 느리다고 알려져있으므로, output을 많이 내보내줘야 하는 상황에서는 반드시 BufferedWriter를 쓰도록 하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

    // 테스트 케이스 개수 k, 정점 개수 v, 간선 개수 e
    static int k, v, e;
    // 리스트 배열을 통해 그래프 생성
    static List<Integer>[] graph;
    // 방문 여부외에 속한 그룹까지 나타내기 위해 int 배열
    static int[] visited;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            v = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            graph = new ArrayList[v+1];
            visited = new int[v+1];

            for (int j = 0; j <= v; j++) {
                graph[j] = new ArrayList<>();
            }

            // 그래프 생성
            for (int j = 0; j < e; j++) {
                st = new StringTokenizer(br.readLine());
                int n1 = Integer.parseInt(st.nextToken());
                int n2 = Integer.parseInt(st.nextToken());
                graph[n1].add(n2);
                graph[n2].add(n1);
            }

            check();
        }
    }

    public static void check() {
        Queue<Integer> q = new LinkedList<>();
        // 웬만한 경우 while 문이 돌고나면 if 문의 다 방문 처리가 되었을 텐데, 그래프가 하나로 연결되지 않고,
        // 두개 이상 따로 분리되어 있을 수 있기 때문에 다시 while 문으로 들어가도록 다 체크해야함
        for (int i = 1; i < v + 1; i++) {
            // 아직 방문하지 않은 노드는 큐에 넣고 방문 여부에 '1'로 기록
            if (visited[i] == 0) {
                q.add(i);
                visited[i] = 1;
            }

            // 상단의 if 문에서 들어온 노드와 연결된 모든 노드를 순회할 예정
            while (!q.isEmpty()) {
                int node = q.poll();
                // 방금 큐에서 꺼낸 노드와 연결된 노드를 모두 for 문 돌림
                for (int j = 0; j < graph[node].size(); j++) {
                    // 연결되어 있는 노드를 아직 방문하지 않았다면 큐에 넣기
                    if (visited[graph[node].get(j)] == 0) {
                        q.offer(graph[node].get(j));
                    }
                    // 연결된 노드간의 visited 값이 같으면 (둘 다 0일리는 없음) => "NO" & return
                    if (visited[graph[node].get(j)] == visited[node]) {
                        System.out.println("NO");
                        return;
                    }
                    // 연결되어 있는 노드를 방문하지 않았는데 현재 노드에는 방문했으므로 다른 값을 배정
                    if (visited[node] == 1 && visited[graph[node].get(j)] == 0) {
                        visited[graph[node].get(j)] = 2;
                    } else if (visited[node] == 2 && visited[graph[node].get(j)] == 0) {
                        visited[graph[node].get(j)] = 1;
                    }
                }
            }
        }
        // 모든 노드 체크 후 "YES"
        System.out.println("YES");
    }
}