[백준]ABCDE - 13023번

https://www.acmicpc.net/problem/13023

13023번: ABCDE

 

문제 분석

친구 관계들이 주어질 때, 아래의 조건에 해당하는 친구 관계가 있는지 구하는 문제입니다.

조건 : 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

처음 시도한 답안

import sys


def main():
    person_count, relation_count = map(int, sys.stdin.readline().split())

    graph = [[] for _ in range(person_count + 1)]

    for _ in range(relation_count):
        friend1, friend2 = map(int, sys.stdin.readline().split())
        graph[friend1].append(friend2)
        graph[friend2].append(friend1)

    def dfs(friends, cnt, path):
        if cnt == 4:
            return True

        for friend in friends:
            if friend not in path:
                path.add(friend)
                flag = dfs(graph[friend], cnt+1, path)
                path.remove(friend)

                if flag:
                    return flag
                
        return False

    for person in range(person_count):
        if dfs(graph[person], 0, {person}):
            print(1)
            return

    print(0)


main()

접근 방법

1. 친구 관계를 이차원 리스트인 그래프에 양방향 형태로 저장합니다.
2. 친구 수만큼 순회합니다.
   1. dfs를 수행한 결과가 True이면 조건에 맞는 친구관계가 존재하는 것이므로 1을 출력합니다.
   2. 아니라면 0을 출력합니다.
3. dfs 내부에서
   
   1. cnt 즉, 탐색한 친구관계의 깊이가 4(0부터 시작)가 되면 True를 리턴합니다.
   2. 등장한 친구가 가지고 있는 친구들을 순회하면서
      1. 방문처리를 하고
      2. DFS를 순회합니다.
      3. 같은 깊이에 있는 다른 친구를 탐색하기 위해 방문처리를 제거합니다.
      4. 만약 dfs를 재귀적으로 호출한 결과가 True라면 조건에 해당하므로 Return 합니다.
      5. 없다면 False를 리턴합니다.

이 문제의 경우 명시된 조건을 이해하는데 헷갈렸던 문제입니다. 결론부터 말하면 특정 친구로부터 친구 관계를 탐색할 때 4번까지 깊게 탐색할 수 있는지를 구하는 것입니다. 즉, dfs 호출의 깊이가 4가 되는 관계가 있는지를 파악하는 문제입니다.

 

처음에는 숫자가 차례로 증감하는 친구 관계가 있는지를 구하는 문제로 잘못 이해했었습니다.