[python] 백준 - 13023. ABCDE

🤔문제 해결

문제는 이어져있는 친구가 4명인지 물어보는 것... ( 헷갈렸다 )

기본적인 DFS 문제이다. 중간에 조건을 줘서 잘 멈춰주기만 한다면 시간초과는 해결될 것이다.

 

💻소스 코드

import sys


def dfs(current, cnt):
    global answer
    if answer == 1:  # 답을 이미 찾았다면 dfs 멈추기
        return

    if cnt == 5:  # 답 찾았을 때 (친구가 4명)
        answer = 1
        return

    visited[current] = 1
    for neighbor in adj[current]:
        if not visited[neighbor]:
            dfs(neighbor, cnt + 1)

    visited[current] = 0

input = sys.stdin.readline
answer = 0

N, M = map(int, input().split())

adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

visited = [0 for _ in range(N)]

for i in range(N):
    if not visited[i]:
        dfs(i, 1)

print(answer)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE