[SWEA|파이썬] 2814. 최장 경로 (D3)

문제

https://tinyurl.com/2nsxaw4h

SW Expert Academy

 

 

🐍파이썬

❌ BFS

from collections import deque
T = int(input())
for test_case in range(1, T+1):
    n, m = map(int, input().split())
    graph = [[]*(n+1) for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    def bfs(x):
        global ans
        queue = deque()
        visited[x] = True
        queue.append(x)
        while queue:
            v = queue.popleft()
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True
                    ans += 1
    arr = []
    for j in range(1, n+1):
        ans = 1
        visited = [False] * (n + 1)
        bfs(j)
        arr.append(ans)
    print("#{} {}".format(test_case, max(arr)))

DFS, BFS 각이 서는 문제는 웬만하면 두 개 방법 모두 사용가능한데 이 문제는 BFS로 도저히 풀이가 안 나와서(테케 5개만 맞음...) 다른 풀이들처럼 DFS로 갈아탔다.

T = int(input())
for test_case in range(1, T+1):
    n, m = map(int, input().split())
    graph = [[]*(n+1) for _ in range(n+1)]
    visited = [False] * (n + 1)	#방문기록
    
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)	#연결된 정점을 이차원배열로 표현
        graph[b].append(a)

    def dfs(x, cnt):
        global ans
        ans = max(ans, cnt)	#최장경로 갱신
        visited[x] = True	#방문체크
        for i in graph[x]:	#정점 x번과 연결된 모든 정점 방문
            if not visited[i]:	#방문한 적 없는 원소만 방문해서
                dfs(i, cnt+1)	#깊이우선탐색
        visited[x] = False	#해당 원소에 대한 다음 경로에서의 dfs를 위해 방문해제

    ans = 1	#경로(=지나는 정점갯수)
    for j in range(1, n+1):	#모든 원소를 방문
        dfs(j, 1)
    print("#{} {}".format(test_case, ans))

모든 원소를 방문해 그 원소부터 시작하는 경로를 확인하고, 그 중 가장 긴 경로를 출력하는 문제이다.

경로의 갯수는 방문한 노드의 갯수이므로 경로를 체크하는 변수 ans는 1부터 시작한다.

dfs 연산에서는 현재 방문한 노드에 대한 방문체크를 하고, 다음 경로의 dfs 연산을 위해 해당 노드의 방문체크를 해제해 주는 것이 중요하다. (ex. 정점 1에서 시작한 경로에도 2가 포함되고 정점 3에서 시작한 경로에도 2가 포함된다면, 1번에서 시작한 dfs연산으로 인해 3번에서 시작한 dfs연산 시 visited[2]는 이미 True이므로 방문목록에서 제외될 수 있음.)