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

문제파악

1. 입력받자마자 순서대로 파악하려했으나 입력이 순서대로 주어지지 않음 -> 모두 입력받고 탐색
2. 연속으로 5명이 연달아 친구관계인 걸 구하는 거니까 DFS로 트리 만들어서 탐색하면 될 것
3. N이 최대 2000이다. -> 행렬로 구현하면 최대 4000000크기의 행렬인데 메모리 제한이 512MB이니 충분할 것.
4. 행렬로 하려고 보니 그럼 아무것도 연결 안된 노드도 N번만큼 탐색해야하니까 연결리스트식으로 구현

코드

import sys

def isEmpty(list):
    for i in list:
        if i:
            return False
    return True
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    f_list = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        f_list[a].append(b)
        f_list[b].append(a)
    is_ans = 0
    for i in range(N):
        stack = [[] for _ in range(5)]
        already_f = [i]
        c = 0
        for x in f_list[i]:
            stack[c].append(x)
        while not isEmpty(stack):
            if not stack[c]:
                c -= 1
                already_f.pop()
                continue
            tmp = stack[c].pop()
            c += 1
            if c == 4:
                is_ans = 1
                break
            already_f.append(tmp)
            for k in f_list[tmp]:
                if k not in already_f:
                    stack[c].append(k)
        if is_ans:
            print(1)
            exit()

    print(0)


main()

리뷰

심하게 틀렸다.
우선 까다로웠던 부분
1. 연결된 친구리스트의 마지막에 도착했을 때, 연속적인 수 즉 스택의 깊이가 4가 되지 않았으면 방문했던 친구와 스택 깊이 수를 하나씩 줄여나가야 하는데 스택으로 구현하다보니 이 부분이 난이도 있었다. 그래서 방문한 노드를 저장하는 리스트를 새로 만들어 관리했다.
2. 스택이 비었으면 while문이 멈춰야한다. 그런데 PEP8에서 추천된 방식으로 if stack:으로 하니까 전부 True로 인식되었다. nested list는 리스트 안의 빈 리스트 때문인지 항상 True로 인식되었다. [찾아본 비슷한 질문글] 그래서 따로 isEmpty라는 함수를 만들어 내부 리스트들을 반복문을 통해 비었는지 확인하였다.

시간이 좀 오래걸려서 시간 최적화하는 방식을 좀 더 생각해봐야겠다.

참고
https://www.i2tutorials.com/how-to-check-if-a-nested-list-is-essentially-empty-in-python/