[SWEA/D3] 2814 최장 경로 / DFS

백준 선행 문제

1260번: DFS와 BFS

문제 바로가기

SW Expert Academy

나의 코드 및 설명

• 선택한 노드에 대하여, 끝까지 탐색해봐야 최장 거리를 비교할 수 있기 때문에 DFS로 문제를 푸는 것이 적합하다.
• 메인 함수 부분에서, for문을 통해 시작점이 되는 노드의 모든 경우의 수를 탐색한다.
• dfs 함수에서 시작점 노드와 방문한 노드를 담을 temp_list를 변수로 받고, dfs를 호출할 때마다 넘겨준다.

##visited 말고 dfs함수의 변수에 정점이 포함되어있는지 확인해야함
def dfs(s, temp_list): #방문한 노드가 담긴 temp_list를 dfs를 호출할때마다 넘겨준다.
    global ans
    ans = max(ans, len(temp_list)) #최대 노드 개수 갱신
    for i in graph[s]:
        if i not in temp_list: #방문한 노드와 연결된 다른 노드가 방문 안했는지 확인(이미 있다면 방문처리 된 것) 
            dfs(i, temp_list+[i])

t = int(input())
for test_case in range(1, t+1):
    n,m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)
    
    ans = 0
    for s in range(1, n+1): #모든 노드를 확인 (시작하는 위치를 준다)
        dfs(s, [s])

    print("#{} {}".format(test_case, ans))

피드백

DFS, BFS를 응용한 문제만 풀다가 이런 기본 문제를 풀려니 어려웠다. 연습을 더 해야할 것 같다. SWEA 문제를 풀며, 이전에 백준 DFS, BFS 기본 문제를 풀었던 것이 기억나서 다시 풀면서 복습했다. DFS와 BFS를 더 공부할 수 있는 좋은 기회가 된 문제이다.