[Python][SWEA] 2814. 최장 경로 D3

 

SW Expert Academy

 

---

🗒️파이썬 코드 풀이

T = int(input())
for tc in range(1,T+1) :
    N,M = map(int,input().split())  # 정점 개수, 간선 정보
    ans = 0
    adjL = [[] * m for m in range(N+1)]  # 정점별 연결 되어있는 것 체크 리스트

    for m in range(M):  # s,e 변수들끼리 서로 연결
        s,e = map(int,input().split())
        adjL[s].append(e)
        adjL[e].append(s) 
    
    def dfs(i,v):
        global ans 
        ans = max(ans,len(v)) # v (방문 리스트) 중 길이 최대값
 
        for k in adjL[i] :  # 정점 내 연결된 정점 반복
            if k not in v : # v (방문 리스트)에 체크 안되어 있는 경우
                dfs(k,v+[k]) # i에 연결된 다음 정점 k로 이동

    for i in range(N+1) :
        dfs(i,[i])
    
    print(f"#{tc} {ans}")

1. 연결된 선들을 기록 할 adjL (2차원 배열) 생성

2. 입력 받은 s,e를 adjL에 서로 각각 연결 

3. 모든 정점 dfs로 순회 ( for i in range(N+1) )

4. ans를 글로벌 변수로 선언하여 최대값 갱신

5. dfs의 매개변수로 입력받은 정점의 리스트를 반복문 돌림

6. k(현재 정점과 연결된 정점)이 v(방문 리스트)에 없다면, 방문리스트에 추가 및 연결 정점 이동

 

📌새로운 개념

알고리즘 문제 중 그래프 문제는 아직 많이 낯설다. 

어떻게 연결된 정점들을 표시할까 했는데, adjL와 같은 2중 배열을 만들어 서로 연결하면 됐다.

 

그리고 dfs라고 다 종료 시점이 있어야 하는 것은 아니다. 

종료를 표시해야하는 것은  dfs() 함수의 매개변수를 끝없이 늘려 줄 때이다. 

 

(언제는 한번 for문을 dfs 안에 넣은적 있었는데,  stack overflow가 됐었다.

함수 밖에서 해야 했는데, 이런것도 조심하자 )

 

익숙하지 않은 코드들이니 자주 봐보자.

---

📚문제

N개의 정점과 M개의 간선으로 구성된 가중치가 없는 무방향 그래프에서의 최장 경로의 길이를 계산하자.

정점의 번호는 1번부터 N번까지 순서대로 부여되어 있다.

경로에는 같은 정점의 번호가 2번 이상 등장할 수 없으며, 경로 상의 인접한 점들 사이에는 반드시 두 정점을 연결하는 간선이 존재해야 한다.

경로의 길이는 경로 상에 등장하는 정점의 개수를 나타낸다.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 개의 자연수 N M(1 ≤ N ≤ 10, 0 ≤ M ≤ 20)이 주어진다.

두 번째 줄부터 M개의 줄에 걸쳐서 그래프의 간선 정보를 나타내는 두 정수 x y(1 ≤ x, y ≤ N)이 주어진다.

x와 y는 서로 다른 정수이며, 두 정점 사이에 여러 간선이 존재할 수 있다.


[출력]

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 그래프에서의 최장 경로의 길이를 출력한다.