2814 최장 경로

최장 경로 URL

Solution

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

public class SW2814 {
    static StringBuilder sb = new StringBuilder();
    static int[][] graph;
    static boolean[] visited;
    static int N, M, answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            graph = new int[N+1][N+1];
            visited = new boolean[N+1];
            answer = 0;

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                graph[x][y] = graph[y][x] = 1; //정점 연결
            }

            for (int i = 1; i <= N; i++) {
                dfs(i, 1);
                visited[i] = false;
            }
            sb.append("#").append(t).append(" ").append(answer).append("\n");
        }
        System.out.println(sb);
    }

    static void dfs(int idx, int cnt) {
        visited[idx] = true;

        for (int i = 1; i <= N; i++) {
            if (graph[idx][i] == 1 && !visited[i]) {
                dfs(i,cnt+1);
                visited[i] = false;
            }
        }
        answer = Math.max(answer, cnt);
    }
}

배운점

먼저 문제를 보고 바로 DFS문제구나 라는걸 깨달았다. 백준 문제풀 당시 많이 보던 유형이기 때문이다.

그러나 방문체크를 밖에서 초기화 반복하며 초기화 해야 정점마다 모든 경우의 수를 체크해 볼 수 있다는 것을 몰랐다.

풀이

1. 우선 정점의 간선을 연결하는 작업이 먼저이기 때문에 graph 배열에 정점끼리 연결하고 1을 넣어 표시한다.

2. 1번부터 N번 까지 반복해야 하므로 visited 배열은 N+1 형태로 만들어준다.

3. 반복문을 1부터 N까지돌며 dfs탐색을 한다. 탐색이 끝나면 visited[i] = false

4. 방문표시를 하고 정점끼리 차례대로 연결한다. cnt는 1부터 시작해야 정점의 개수를 나타낼 수 있다.

5. 노드마다 최장 경로는 answer에 담아준다.