[SW Expert Academy, SWEA 2814] 최장 경로 (python)

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

SW Expert Academy

---

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

728x90

---

내 생각

아... SWEA 문제는 풀면 풀 수록 느끼는 건데, 문제를 너무 이해하기 어렵게 써둔다..

나만 그렇게 느끼나...

문제를 직관적으로 이해할 수 없게 줄줄 써둔 느낌이랄까?

(물론 나도 내가 생각한 것들을 글로 남들이 보고 이해하기 쉽게 잘 못쓰는 편이긴 하지만, 문제를 내는 사람은 그러면 안 되지!!!)

이런 문제들은 그래도 테스트 케이스 보고 어느 정도 감이 잡히는데, 테스트 케이스도 너무 빈약하게 주고 마음에 안 드는구만!

 

암튼 문제 이해한 대로 써보자면

조건: 경로에는 같은 정점의 번호가 2번 이상 등장할 수 없다.

만약 다음과 같은 정점과 간선들이 있다면,

n = 5, m = 5

1 2

2 3

3 4

4 1

1 5

조건에 만족하기 위해서는 다음 예와 같은 경로여야 한다.

ex)

1 -> 2 -> 3 -> 4

2 -> 3 -> 4 -> 1 -> 5

조건을 위배하는 경로는 다음과 같다.

ex)

1 -> 2 -> 3 -> 4 -> 1 -> 5

정점 1이 2번 이상 등장했으므로 위의 예는 조건을 위배했다고 할 수 있다.

 

문제에서 [입력] 부분에 x와 y는 서로 다른 정수이며, 두 정점 사이에 여러 간선이 존재할 수 있다.

이 부분은 어차피 같은 정점이 2번 이상 오지 못하는데 이 문제에서 왜 필요한 설명인지 모르겠다.

 

이 문제에서 핵심은 DFS를 어느 정점에서 시작하느냐에 따라 최장 경로가 달라질 수 있다.

따라서 DFS를 모든 정점에서 시작해보아야 최장 거리를 구할 수 있다는 것이다.

(위의 예에서처럼 정점1에서 시작하면 count = 4, 정점2에서 시작하면 count = 5가 되는 것을 보면 알 수 있다.)

def dfs(v, count):
    global max_count
    # 방문 처리
    visited[v] = True
    # v에 연결되어 있는 점들 중
    for i in graph[v]:
        # 아직 방문하지 않았다면
        if visited[i] == False:
            # 방문한다
            dfs(i, count + 1)
    # 더 이상 방문할 수 있는 점이 없다면
    # 방문처리를 취소해줌. (다른 경로에서 지나갈 수도 있기 때문에)
    visited[v] = False

    # 이때 max_count보다 현재의 경로의 길이가 더 크다면
    if count > max_count:
        # max_count 갱신
        max_count = count

# 테스트 케이스의 수 t
t = int(input())

for test_case in range(1, t + 1):
    n, m = map(int, input().split())
    # 경로를 넣을 배열
    graph = [[] for _ in range(n + 1)]
    # 방문 처리 배열
    visited = [False] * (n + 1)

    # 간선 정보 입력
    for i in range(m):
        x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)

    # 최장 간선의 길이 구하기
    count, max_count = 0, 0

    for i in range(1, n + 1):
        dfs(i, 1)

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