[백준][13023] ABCDE

• 문제
  • 13023번: ABCDE
• 해결

import sys

person_count, relation_count = [int(x) for x in sys.stdin.readline().strip().split()]

data = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]

relation = {k: [] for k in range(person_count)}

for x in data:
    relation[x[0]].append(x[1])
    relation[x[1]].append(x[0])

relation = {k: set(v) for k, v in relation.items()}

for k in relation.keys():
    for i in relation[k] - set([k]):
        for j in relation[i] - set([k, i]):
            for u in relation[j] - set([k, i, j]):
                if len(relation[u] - set([k, i, j, u])):
                    print(1)
                    exit()
print(0)

• 포인트
  • 길이가 5인 path의 존재인 문제인데 길이가 5로 고정되어 네번의 for-loop로 해결
  • dfs로 길이가 5되는 것 찾아도 될 듯