[삼성 sw 파이썬] 2814 최장 경로

[삼성 sw 파이썬] 2814 최장 경로

문제

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

정점의 번호 1부터 N번까지 순서대로 부여된다.

경로에는 같은 정점의 번호가 2번 이상 등장할 수 없다 경로 상의 인접한 점들 사이에는 반드시 간선이 존재한다.

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

 

입력

첫 줄에는 테스트케이스가 주어진다.

각 테스트 케이이스의 첫 번 줄에는 두 개의 자연수 N, M이 주어진다.

두 번째 줄부터 M개의 줄에 걸쳐서 그래프의 간선 정보를 나타낸다.

풀이

문제에서 가중치가 없는 무방향 그래프라고 주어졌으면 경로상의 가장 경로를 탐색하는 완전 탐색 문제로

DFS나  BFS를 이용아여 문제를 풀 수 있다.

나는 DFS르 이용하여 문제를 풀었다.

def dfs(s,count):
    global ans
    if ans<count:
        ans=count
    v[s]=True
    for i in g[s]:
        if not v[i]:
            dfs(i,count+1)
            v[i]=False

일반적인 DFS코드와는 다르게 방문하고 나면 그 루트 탐색이 끝나면 방문했던걸 지워야 한다 왜냐하면 다른 간선을 이용하여 그 정점에 도달할 수 있기 때문이면 우리가 찾아야 하는 거는 최장 거리이기 이에 DFS가 반복할 때만 COUNT값을 +1을 해주면 최댓값을 계속하여 찾을 수 있다.

또한 DFS를 모든 정점에서도 다 돌려야 한다.

1번 정점에서도 돌려보고 2번 정점에서도 돌려봐야지 가장 긴 거리를 알 수 있다.

코드

def dfs(s,count):
    global ans
    if ans<count:
        ans=count
    v[s]=True
    for i in g[s]:
        if not v[i]:

            dfs(i,count+1)
            v[i]=False



test=int(input())

for t in range(test):
    n,m=map(int,input().split())
    g=[[] for _ in range(n+1)]
    ans=0
    for i in range(m):
        a,b=map(int,input().split())
        g[a].append(b)
        g[b].append(a)
    for j in range(1,n+1):
        v=[False]*(n+1)
        dfs(j,1)
    print(f"#{t+1} {ans}")