[swea 2814-파이썬]최장 경로

swea 2814 최장 경로

사용언어 : PYTHON

풀이

무방향 그래프에서 최장 경로의 길이를 구해아 한다.

최장경로는 그래프의 정점들 중 더 이상 이동할 수 없을때 까지 탐색한 경로 길이 중 가장 큰 값이다.

더 이상 이동할 수 없을때 까지 탐색하기 위해 dfs를 활용하였다.

---

1.우선 입력이 연결된 간선들로 주어지기 때문에 이들을 2차원 행렬로 정리해서 그래프로 표현하였다.

👇

for _ in range(M):
    l.append(list(map(int,input().split()))) # 입력으로 주어지는 연결된 간선

for j in l: # 2차원 행렬의 그래프로 표현
    graph[j[0]].append(j[1])
    graph[j[1]].append(j[0])

2.다음으로 모든 정점들을 돌아가며 dfs를 수행한다.

dfs함수 에서는 주어진 정점으로 부터 이동할 수 있는 모든 경로를 탐색하며 count한 값을 answer리스트에 append한다.

👇

for j in range(1,N+1):
    visited=[False]*(N+1)
    cnt=0
    dfs(j)

3.dfs함수

def dfs(i):
    global cnt

    visited[i]=True
    cnt+=1
    flag=1

    for p in graph[i]:
        if visited[p]==False:
            flag=0
            dfs(p)
            visited[p]=False
            cnt-=1


    if flag==1:
        answer.append(cnt)        

    return

시작할 노드를 매개변수로 받는다.

방문한 노드를 visited리스트에 기록한다.

한 노드를 방문했으므로 카운트 값을 1 증가 시킨다.

🎈flag변수 : 더 이상 이동할 수 없을때(그래프의 가장 끝 점으로 이동했을때)를 체크하기 위한 변수
체크하는 이유는 끝 점에 도달했을때 그 경로의 count값을 answer리스트에 append해야 하기 때문이다.

graph리스트를 활용하여 인접한 노드들 중 False(방문하지 않은 노드)이면 flag변수를 0으로 만들고(최소한 하나 이상의 노드는 방문 했다는 표시) dfs를 재귀로 수행한다.

재귀로 실행되었던 dfs가 return되면 visited[p]=False로 다시 방문기록을 없애준다.

또한 cnt값을 -1 해서 방문한 노드의 갯수를 갱신한다.

코드

def dfs(i):
    global cnt

    visited[i]=True
    cnt+=1
    flag=1

    for p in graph[i]:
        if visited[p]==False:
            flag=0
            dfs(p)
            visited[p]=False
            cnt-=1


    if flag==1:
        answer.append(cnt)        

    return


T=int(input())

for i in range(T):
    N,M=map(int,input().split())
    graph=[list() for _ in range(N+1)]
    l=[]
    answer=[]

    for _ in range(M):
        l.append(list(map(int,input().split())))

    for j in l:
        graph[j[0]].append(j[1])
        graph[j[1]].append(j[0])

    for j in range(1,N+1):
        visited=[False]*(N+1)
        cnt=0
        dfs(j)

    print('#{} {}'.format((i+1),max(answer)))