[SWEA] 파이썬 2814. 최장 경로 | DFS

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=PYTHON&select-1=3&pageSize=10&pageIndex=2 

SW Expert Academy

 

 

문제 해결 포인트

- BFS 문제인줄 알았으나 DFS로 밖에 풀 수 없는 문제

- 간선을 인접 행렬 또는 인접 리스트로 저장

- 방문한 정점에 대해 표시해 놓을 리스트

- 어떤 노드부터 시작해야지 가장 길지 알 수 없으므로 모든 정점에 대해 시작노드로 탐색

- 부모 노드로 올라올 때 방문표시 해제

- 가장 깊이 DFS를 들어간 경우가 정답

 

 

작성 코드

 

# DFS 풀이
def dfs(vert, depth):
    global result
    if depth > result: result = depth  # 지금까지 경로보다 길다면
    for v in vertexes[vert]:  # 해당 정점에 대해 연결된 모든 정점 탐색
        if not visited[v]:  # 아직 방문되지 않았다면
            visited[vert] = True  # 방문 표시
            dfs(v, depth+1)
            visited[vert] = False  # 방문 해제


for test in range(1, int(input())+1):
    N, M = list(map(int, input().split()))
    vertexes = [[] for _ in range(N+1)]
    result = 0

    for i in range(M):  # 모든 간선을 인접 리스트화(무방향이므로 두 정점 각각 연결)
        start, end = list(map(int, input().split()))
        vertexes[start].append(end)
        vertexes[end].append(start)

    visited = [False]*(N+1)  # 방문한 정점 표시
    for vertex in range(1, N+1):  # 처음 방문할 정점 선택
        visited[vertex] = True
        dfs(vertex, 1)

    print("#{} {}".format(test, result))

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

---

REFERENCE

https://wizdom.tistory.com/238