[swea | 2814] 최장경로(DFS, 그래프)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE 

SW Expert Academy

 

N개의 정점과 M개의 간선으로 구성된 가중치가 없는 무방향 그래프에서의 최장 경로의 길이를 계산하자.

정점의 번호는 1번부터 N번까지 순서대로 부여되어 있다.

경로에는 같은 정점의 번호가 2번 이상 등장할 수 없으며, 경로 상의 인접한 점들 사이에는 반드시 두 정점을 연결하는 간선이 존재해야 한다.

경로의 길이는 경로 상에 등장하는 정점의 개수를 나타낸다.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 개의 자연수 N M(1 ≤ N ≤ 10, 0 ≤ M ≤ 20)이 주어진다.

두 번째 줄부터 M개의 줄에 걸쳐서 그래프의 간선 정보를 나타내는 두 정수 x y(1 ≤ x, y ≤ N)이 주어진다.

x와 y는 서로 다른 정수이며, 두 정점 사이에 여러 간선이 존재할 수 있다.


[출력]

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 그래프에서의 최장 경로의 길이를 출력한다.
 

입력2
1 0
3 2
1 2
3 2

 

출력#1 1
#2 3

 

문제풀이

import sys
from collections import deque
sys.stdin = open("20220725_swea_2814_최장경로.txt", "r")

def DFS(now, count) :
    global max_count

    visited[now] = True

    if count > max_count :
        max_count = count

    for next in graph[now] :
        if visited[next] is False :
            DFS(next, count+1)
            visited[next] = False

test_case = int(input())

for test in range(test_case) :
    node_cnt, line_cnt = map(int, input().split())
    graph = [[] for _ in range(node_cnt + 1)]
    visited = [False] * (node_cnt + 1)
    max_count = 0

    #인접리스트 생성
    for _ in range(line_cnt) :
        node, line = map(int, input().split())
        graph[node].append(line)
        graph[line].append(node)

    #시작점을 변경하면서 인접 리스트 그래프를 방문한다.
    for i in range(1, node_cnt + 1) :
        visited[i] = True
        DFS(i, 1)
        visited[i] = False
        
    print(f'#{test+1} {max_count}')

#n개의 정점
#m개의 간선
#무방향 그래프
#최장 경로의 길이 계산

# 2         <--- 테스트케이스 개수
# 1 0       <--- n, m
# 3 2       <--- 노드 개수, 라인 개수
# 1 2       <--- n, m
# 3 2       <--- 노드 개수, 라인 개수