[JAVA] 13244 - Tree 💛4 : 트리 자료구조의 특징을 알고 있는지 물어보는 문제

들어가며

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

처음에 문제가 영어로 되어 있길래 매우 당황했다 ㅎㅎ. 심호흡하고 한문장씩 읽어보면 결론은 트리 자료구조에 대한 설명을 해준다. 예전에 들었던 자료구조 수업 내용이 생각났다! 문제는 입력으로 주어지는 노드들간의 연결 정보를 통해 tree인지 graph인지 출력하는 문제였다.

본문으로

처음에는 대수롭지 않게 아무 노드에서 재귀적 탐색을 들어갔을 때(DFS) 다 연결되면 tree고,,, 안되고 끊긴다면 graph구나 했다. 하지만 양방향 간선으로 이루어진 그래프에서 DFS로는 왼쪽 그래프는 tree인지 graph인지 구분이 가능하지만, 오른쪽 그래프 즉 사이클이 생기는 그래프에서는 구분이 불가능하다. (둘다 다 탐색할텐데 오른쪽은 tree가 아니지 않은가!!)

그래서 자신있게 인접리스트로 양방향 간선을 이루는 형식으로 그래프를 구성했는데... 이게 참.. 사이클을 발견하는 로직을 생각하기가 너무너무 어려웟다..

---

이것저것 해보다가 결론 내린 것은 다음과 같다.(사실 전공수업 때 배웠던 것을 떠올렸다.)

트리의 간선의 개수는 노드의 개수 - 1 이다. 즉 문제에서는 M = N - 1 을 이루어야 사이클이 없는 트리라고 표현할 수 있다.

정답은 아래와 같이 제출했다.

public class Main {

    static int T, N, M;
    static List<Integer>[] adjList;
    static int[] visited;

    static int dfs(int idx) {
        int cnt = 1;
        visited[idx] = 1;
        for (int i = 0; i < adjList[idx].size(); i++) {
            int next = adjList[idx].get(i);
            if (visited[next] == 0) {
                cnt += dfs(next);
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(bf.readLine());

        while (T-- > 0) {
            N = Integer.parseInt(bf.readLine());
            M = Integer.parseInt(bf.readLine());
            adjList = new ArrayList[N + 1];
            visited = new int[N + 1];
            for (int i = 0; i < N + 1; i++) {
                adjList[i] = new ArrayList<>();
            }
            for (int i = 0; i < M; i++) {
                StringTokenizer st = new StringTokenizer(bf.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                adjList[a].add(b);
                adjList[b].add(a);
            }

            if (M != N - 1 || dfs(1) != N) {
                System.out.println("graph");
            } else {
                System.out.println("tree");
            }

        }

    }
}

마무리하며

영어로 된 백준 문제는 처음 풀어보기도 했고, 까먹고 있었던 트리의 개념을 다시 한번 떠올리게 해준 고마운 문제다! 

CS지식 공부한 느낌이라 좋다 ㅎㅎ. 전공자라면 알고 있어야 하는 내용이지 않겠는가! 

앞으로도 파이팅 🔥