[SWEA/Python] 2814. 최장 경로

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 처음엔 스택을 이용해서 dfs를 실행해줬었는데, 방문체크를 해제할 수가 없어서 재귀로 바꾼후, 완전탐색을 해줬다.
2. 재귀로 구현하면 목적지를 어떻게 설정하지?가 문제였는데, 그냥 함수가 실행될 때마다 경로에 속한 정점의 개수를 갱신해주면 된다.

 

📌 코드

import sys
sys.stdin = open('input.txt')

def dfs(v, cnt):
    global max_cnt

    max_cnt = max(max_cnt, cnt)

    for w in range(1, N+1):
        if graph[v][w] and not visited[w]:
            visited[w] = 1
            dfs(w, cnt+1)    
            visited[w] = 0


T = int(input())

for t in range(1, T+1):
    N, M = map(int, input().split())
    graph = [[0 for _ in range(N+1)] for _ in range(N+1)]

    for _ in range(M):
        x, y = map(int, input().split())
        graph[x][y] = 1
        graph[y][x] = 1
    
    max_cnt = 1
    for i in range(1, N+1):
        visited = [0 for _ in range(N+1)]
        visited[i] = 1
        dfs(i, 1)
        
    print('#{} {}'.format(t, max_cnt))