최장경로 Python(SW Expert Academy)

난이도 : D3

문제번호 :2814

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

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

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

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

---

2. 문제풀이

시작 노드마다 최대 이동거리가 달라질 수가 있다. 따라서 반복문을 이용하여 각 노드마다 시작을 했다. 이동 방식은 사용한 노드를 체크하고 이동시 사용한 노드로 가려하면 무시하는 방식으로 풀었다. 이동시 카운트를 하며 카운트된 값이 저장된 값보다 커지면 갱신을 한다. 개인적으로 그래프 표현을 자기가 사용하기 쉽도록 사용하는게 좋은것 같다.

 

---

3. 소스코드

#D3 2814 최장경로
 
def dfs(idx, ans):
    global answer
    #탐색한 노드는 체크하고
    visited[idx] = 0
    #이동횟수 증가
    ans += 1
    #최댓값 갱신
    if answer < ans: answer = ans
    #이동가능 노드 확인
    for i in graph[idx]:
        #이동가능하면 이동
        if visited[i]: dfs(i, ans)
    #사용 해제
    visited[idx] = 1
 
for t in range(1, int(input()) + 1):
    #노드와 간선 정보를 받고
    N, M = map(int, input().split())
    #방문 배열 만들고
    visited = [1 for _ in range(N+1)]
    #입력받아서
    temp = [list(map(int, input().split())) for _ in range(M)]
    #쉽게 사용하기위한 데이터 편집하기
    graph = [[] for _ in range(N+1)]
    answer = 0
    #노드간 이동 경로 표시
    for a, b, in temp:
        graph[a].append(b)
        graph[b].append(a)
    #시작노드를 다르게해서 최대 길이 찾기
    for i in range(N): dfs(i, 0)
    print('#{} {}'.format(t, answer))