[SWEA] 2814 : 최장 경로 - Python

문제 : 최장경로

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부터 시작한다)를 출력하고, 그래프에서의 최장 경로의 길이를 출력한다.

import sys
sys.stdin = open("input.text", "rt")

def dfs(v, sum): # 현재 g에서 최장거리 구하기.
    global res
    if sum > res: # 먼저 최댓값을 넘었는지 확인.
        res = sum
    else:
        for node in g[v]: # 인접노드들 하나씩 확인
            if ch[node] == 0: # 아직 방문 전
                ch[node] = 1
                dfs(node, sum + 1)
                ch[node] = 0 # 백트랙킹 시 반환



T = int(input())
for t in range(1,T+1):
    n,m = map(int, input().split())
    g = [[] for _ in range(n+1)]
    res = 0
    for _ in range(m):
        x,y = map(int, input().split())
        g[x].append(y)
        g[y].append(x)
    ch = [0] * (n+1)
    for i in range(1,n+1):
        ch[i] = 1
        dfs(i, 1)
        ch[i] = 0
    print(f"#{t} {res}")

코멘트

경로에는 같은 정점의 번호가 2번 이상 등장할 수 없다. 즉 중복 체크를 했어야 함.

• 그거에 더해서 N,M의 크기가 작기에 모든 경우 따질 수 있을 것 같은 생각..?
• 거기에 더해 뭔가 그래프 깊이 우선 탐색 냄새...

근데 안 좋았던 건 테스트 케이스를 보고 개수를 알 수 있었음. 결국 노드 1개, 간선 0개 여도 최장거리 1로 치는 것을 토대로 코드 짰으면 됐음.

• DFS는 백트랙킹 시 원상복구 유의!

여기서 실수한게

for i in range(1,n+1):
        ch[i] = 1
        dfs(i, 1)
        ch[i] = 0

해당 부분에서 그냥 ch[i] = 1 없이 바로 dfs(i,i+1)을 진행했다.
그래서 계속 틀렸는데.. 해당 부분에서도 시작 부분은 체크 표시 하고 들어갔어야 했다.
아니면 바로 방문처리를 했어도 OK !!!!

• 하지만 그렇게 하면 마지막에도 방문 해제 해줘야 해서 현재 코드가 가장 익숙함.