[파이썬] 백준 13023 - ABCDE

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

13023번: ABCDE

 

문제를 이해하는데 시간이 걸렸는데 A,B,C,D,E가 아무 숫자나 와도 되고 A-B-C-D-E의 친구관계를 가지는 것이 문제 조건이다. 결국 그래프탐색에 있어서 5개의 노드를 거치면 1을 출력하면 되는 것이다.

 

7에서 시작하면 최대 깊이는 4 (7-3-4-0)이지만 2에서 시작하면 5(2-7-3-4-0)이다.

그냥 visited 배열을 활용한 backtracking으로 했는데 1.2초 걸려서 통과했다.

 

import sys
def input():
    return sys.stdin.readline().rstrip()

def backtracking(idx, now):
    if now == 4:
        print(1)
        exit()
    for i in adj[idx]:
        if not visited[i]:
            visited[i] = True
            backtracking(i, now+1)
            visited[i] = False

N,M = map(int,input().split())
adj = [[] for _ in range(N)]
visited = [False] * N

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

for i in range(N):
    visited[i] = True
    backtracking(i, 0)
    visited[i] = False

print(0)

exit를 활용해서 프로그램을 종료시키는 형식으로 했다.