11581 구호물자 Python

✅ 11581 구호물자 Python

📊 문제설명

서기 2050년, 인천에 강력한 폭풍이 몰아쳐 도로와 표지판이 모두 손상된 상황입니다.
1번 교차로에서 출발해 N번 교차로(대피소)까지 구호물자를 보내야 하는데, 도로가 일방통행이고 표지판이 없어 트럭 운전사가 길을 제대로 선택하지 못합니다.

만약 어떤 길을 선택하더라도 이미 지나온 교차로를 다시 방문하는 일이 발생하면, 연료가 부족해 대피소에 도달하지 못할 가능성이 있습니다.

이 문제는 1번 교차로에서 N번 교차로까지 가는 모든 경로에서 같은 교차로를 다시 방문하는 경우가 있는지 없는지를 판단하는 것입니다.

💡 아이디어

1. 그래프 모델링
   문제에서 주어진 교차로와 도로를 방향 그래프로 모델링합니다.
   각 교차로는 노드, 도로는 방향 간선입니다.
2. 사이클 판단 조건
   “어떤 경로를 선택하더라도 교차로를 다시 방문하지 않는” 경우를 찾기 때문에
   1번 교차로에서 시작해 N번 교차로에 도착하는 모든 경로에서 사이클(재방문)이 없음을 확인해야 합니다.
3. DFS와 사이클 탐지
   DFS로 경로를 탐색할 때, 방문한 노드를 다시 방문하면 사이클이 생긴 것입니다.
   이를 탐지하기 위해 방문상태 배열(check)을 두 가지 상태로 구분합니다:
   
   • 방문 중 (재귀 호출 스택에 있음) = 1
   • 방문 완료 (재귀 종료 후) = 0
   DFS 탐색 중 이미 방문 중인 노드를 다시 만나면 사이클 존재.
4. N번 교차로는 대피소로, 연결 없음
   N번 교차로는 도착점이며 연결 도로가 없으므로 DFS가 여기서 종료됩니다.
5. 결과 판단
   DFS 도중 사이클이 발견되면 "CYCLE" 출력
   아니면 "NO CYCLE" 출력

📜 전체코드

import sys
sys.setrecursionlimit(10**7)

arr = [[0 for _ in range(100)] for _ in range(100)]
check = [0 for _ in range(100)]
check_cycle = False

def DFS(n):
    global check_cycle
    check[n] = 1

    for i in range(1, N+1):
        if arr[n][i] == 1:
            if check[i] == 1:
                check_cycle = True
                return
            DFS(i)
            if check_cycle:
                return

    check[n] = 0

N = int(input())

for i in range(1, N):
    M = int(input())
    inputs = list(map(int, input().split()))
    for input_node in inputs:
        arr[i][input_node] = 1

DFS(1)

if check_cycle:
    print("CYCLE")
else:
    print("NO CYCLE")

🔍 개별코드 설명

import sys

Python의 sys 모듈을 불러옵니다.
재귀 호출 제한을 변경하기 위해 필요합니다.

sys.setrecursionlimit(10**7)

Python의 기본 재귀 깊이 제한(기본 1000)을 늘려서 깊은 DFS 탐색이 가능하도록 설정합니다.
최대 10^7까지 재귀 호출을 허용합니다.

arr = [[0 for _ in range(100)] for _ in range(100)]

최대 100개의 교차로에 대해 인접 행렬로 그래프를 표현합니다.
arr[i][j]가 1이면 i번 교차로에서 j번 교차로로 가는 도로가 있다는 뜻입니다.
리스트 컴프리헨션을 사용해 모든 값을 0으로 초기화합니다.

check = [0 for _ in range(100)]

각 노드(교차로)의 방문 상태를 저장하는 배열입니다.
0: 방문 안 함, 1: 현재 DFS 경로상에서 방문 중임(재귀 스택 내에 있음)
리스트 컴프리헨션을 사용해 초기값을 0으로 설정합니다.

check_cycle = False

사이클(재방문)이 발견되었는지 여부를 저장하는 변수입니다.
사이클 발견 시 True로 변경합니다.

def DFS(n):

n번 교차로부터 시작해 DFS(깊이 우선 탐색)를 수행하는 함수 선언입니다.

global check_cycle

check_cycle 변수를 함수 내에서 전역 변수로 사용하기 위해 선언합니다.

check[n] = 1

현재 노드 n을 방문 중임을 표시합니다.
즉, 현재 DFS 재귀 호출 경로에 포함되어 있다는 뜻입니다.

for i in range(1, N+1):

1번부터 N번까지 모든 교차로에 대해 반복합니다.
n에서 i로 가는 도로가 있는지 확인하기 위함입니다.

if arr[n][i] == 1:

n에서 i로 가는 도로가 있으면 조건문 안을 실행합니다.
즉, n과 i가 연결되어 있는 경우입니다.

if check[i] == 1:

i번 노드가 이미 방문 중이면 (현재 DFS 경로상에 있다면)
사이클이 발생했음을 의미합니다.

check_cycle = True; return

사이클이 발견되었으므로 check_cycle 변수를 True로 바꾸고
DFS 탐색을 즉시 종료합니다.

DFS(i); if check_cycle: return

i번 노드를 방문하지 않았다면 (즉, check[i] == 0) 재귀적으로 DFS를 수행합니다.
DFS 실행 후 사이클 발견 여부를 체크하고, 발견 시 즉시 종료합니다.

check[n] = 0

현재 노드 n에서 모든 인접 노드를 탐색한 후,
DFS 경로상에서 빠져나간 것을 의미하며 방문 상태를 ‘방문 안 함’으로 되돌립니다.
이는 같은 노드를 다른 경로에서 재방문할 수 있도록 하기 위한 조치입니다.

N = int(input())

전체 교차로 수를 입력받아 N에 저장합니다.

for i in range(1, N):

1번부터 N-1번 교차로까지 차례대로 연결 정보를 입력받습니다.
N번 교차로는 대피소이므로 연결 정보가 없습니다.

M = int(input())

현재 i번 교차로에서 갈 수 있는 교차로 수를 입력받습니다.

inputs = list(map(int, input().split()))

현재 i번 노드와 연결된 교차로 번호들을 공백으로 구분된 입력으로 받아 리스트로 변환합니다.

for input_node in inputs: arr[i][input_node] = 1

연결된 교차로 번호를 순회하며 인접 행렬에 도로가 있음을 표시합니다.

DFS(1)

1번 교차로부터 DFS 탐색을 시작합니다.

if check_cycle: print("CYCLE") else: print("NO CYCLE")

DFS 종료 후 사이클 존재 여부에 따라 결과를 출력합니다.
사이클 발견 시 "CYCLE" 출력
아니면 "NO CYCLE" 출력