[백준] 구호물자 (Python)

문제

서기 2050년 엄청나게 강력한 폭풍이 인천을 강타했다. 강력한 폭풍의 영향으로 모든 사람은 대피소로 대피하였으며, 많은 도로가 유실되었다. 그나마 남아있는 도로도 모든 표지판과 가로등이 작동을 멈춰 제대로 된 길을 찾기란 불가능에 가까웠다.

이런 심각한 상황에 민지는 대피소에 구명 물자를 보내려고 한다. 서기 2050년 인천의 모든 길은 교차로와 도로만으로 이루어져 있다. 한 교차로와 다른 교차로는 일방통행 도로로 연결되어 있으며, 한 교차로와 여러 교차로가 연결될 수 있다. 그리고 도로에 한번 진입하면 교차로에 도착할 때까지 도로를 벗어날 수 없다.

민지는 구호물자로 가득 찬 트럭을 출발시키려고 했지만, 운행을 거부한 트럭운전사들 때문에 난관에 봉착했다. 강력한 폭풍의 영향으로 내비게이션은 정확하지 않고, 도로를 구분할 수 있는 표지판이 망가졌기 때문에 트럭운전사들은 교차로에서 어떤 도로를 선택해야 할지 모른다. 이러한 상황에서 특정 도로를 임의로 선택하면 이미 지나쳤던 교차로를 또다시 방문하는 일이 발생할 수 있고, 만약 그런 상황이 발생하면 트럭의 기름이 부족해 대피소에 도착하지 못할 수 있다.

대피소에 반드시 구호물자를 보내야 한다고 생각하는 민지는 현재 위치인 1번 교차로에서 대피소가 있는 N번 교차로까지 어떤 도로를 선택하며 가더라도 지나친 교차로를 다시 방문하지 않는다는 것을 증명해 트럭 운전사들을 설득하려 한다.

위 그림은 대피소가 3번에 있다고 했을 때 가능한 두 가지 모양이다. 왼쪽 그림에서는 어떠한 도로를 선택하더라도 지나친 교차로를 다시 방문하지 않고 대피소가 있는 3번에 무사히 도착할 수 있다. 하지만 오른쪽 그림에서는 방문했던 교차로를 다시 방문할 가능성이 있다.

민지를 도와 어떠한 길을 선택하더라도 같은 교차로를 다시 방문하는 경우가 있는지 없는지를 판단하는 프로그램을 작성하자.

입력

첫 번째 줄에 교차로의 수 N(1 ≤ N ≤ 100)이 주어진다. 그다음에 1번 교차로부터 N-1번 교차로의 상태가 각각 두 줄에 걸쳐 차례대로 주어진다. (1 ≤ i ≤ N-1)번째 교차로와 연결된 교차로의 수 Mi(0 ≤ Mi ≤ N)가 주어지고 그다음 줄에는 i번째에서 갈 수 있는 교차로의 번호 Ci(1 ≤ Ci ≤ N)가 주어진다. N번 교차로는 대피소가 있는 곳이기 때문에 연결 상태가 주어지지 않는다. 구호물자가 출발하는 장소는 항상 1번이며 대피소가 있는 곳 역시 항상 N번이다.

출력

1번 교차로에서 N번 교차로까지 가는 과정 중 지나쳤던 교차로를 다시 방문하는 경우가 생길 수 있으면 CYCLE, 그렇지 않다면 NO CYCLE을 출력한다.

예제 입력 1

3
2
2 3
1
3

예제 출력 1

NO CYCLE

예제 입력 2

3
2
2 3
2
1 3

예제 출력 2

CYCLE

문제 정리

# 인천 모든 길 - 교차로 / 도로
# 한 교차로와 다른 교차로 - 일방통행 도로
# 한 교차로와 여러 교차로 연걸 가능
# 도로 진입 시, 교차로 도착할 때까지 도로 못 벗어남

교차로는 이어져있어도 한쪽 방향만 갈 수도 있음

# N 교차로의 수
# 1번부터 N-1번 교차로의 상태 두 줄에 걸쳐 주어짐
# 그림판으로 구조 파악 완료
# 현재 위치 1이라면 3번째 줄에 적힌 2와 3에 갈 수 있음
# 그 다음 값이 3이면 stop
# 2일땐 방문한적있는 값이 1이 되었다면 stop
# 즉 현재 위치 담을 queue와 방문기록의 visited 둘다 만들어야함

첫번째 풀이

맨 처음 해석했을 땐, 그냥 1에서2로 가고 2에서 1로 가는 숫자를 찾으면 그건 CYCLE이지 않을까? 왜냐면 문제 특성상 원하는 위치 N까지는 무조건 갈 것이지에 못가는 경우는 없다고 생각해서이다.

즉,
2
2 3

1에선 2개의 교차로가있고 2,3에 접근할 수 있는데

1
3

2에선 1개의 교차로에 3밖에 못가므로,

만약에 여기서 2에서 1 3이 있었으면 양방향이 가능해서 CYCLE이다 생각했었다.

# import sys
# from collections import deque

# N = int(sys.stdin.readline())
# course_list = []

# for _ in range((N-1)*2):
#   course_list.append(sys.stdin.readline().strip().split())
  
# visited = [False]* (N+1)
# queue = deque([1])

# # 00숫자가 적혀있다면 그만큼의 숫자가 나열 됨
# # 이 둘의 관계를 정의해줘야함

# while queue:
#   current_number = queue.popleft()
#   visited[current_number] = True
  
#   for i in range(len(course_list)):
#     for j in range(int(course_list[i])):

근데 머리에 떠오른 생각만가지고 어떻게 그 숫자에 접근할지 감이 안잡혔다.

두번째 풀이

# import sys
# from collections import deque

# N = int(sys.stdin.readline())
# course_list = []

# for _ in range((N-1)*2):
#   course_list.append(sys.stdin.readline().strip().split())
  
# visited = [False]* (N+1)
# queue = deque([1])

# # 00숫자가 적혀있다면 그만큼의 숫자가 나열 됨
# # 이 둘의 관계를 정의해줘야함

# while queue:
#   current_number = queue.popleft()
#   visited[current_number] = True
  
#   for i in range(len(course_list)):
#     for j in range(int(course_list[i])):

00숫자가 3번째 5번째 인덱스에 위치하니까 거기서 숫자를 뽑아내서 겹치면 되지 않을까?라고 생각했었지만 여기엔
치명적인 오류가 있는게,
1에서 2로갈수 있고 2에서 1로 갈 수 있다치면, 그 숫자는 1 과 2로 적혀있기 때문에, 양방향 교차로가 성립되더라도, 그걸 숫자로는 다르게 표현되기 때문에 저런 방식으로는 문제 풀이가 더이상 떠오르지 않았다.

최종 풀이

import sys

# 한 줄 씩 읽어오기
input = sys.stdin.readline
# 거리 배열에서 연결 안되어 있을 때 큰 값 설정
# 즉 거리가 엄청 멀리 있다 == 연결 되어 있지 않다
INF = 100000

# 첫 줄 N
N = int(input())
# 사이클 존재 여부 추적 변수
cycle = False

# 단순 dfs가 아닌 알고리즘 사용 위해 교차로 간 거리 저장
# 3x3 즉 첫번째 인덱스에 3개의 요소 이런식으로 이중 리스트로 담겨있음
# [[100000,100000,100000],...] 이런 느낌으로
# 그래야 첫번째 점에서 다른 점으로 갈때 코스가 있으면 값 변경해줘서 체크해줄 수 있음
cross = [[INF for _ in range(N)]for _ in range(N)]

# 마지막 교차로 n이 대피소여서 연결 정보 탐색 필요 x
for i in range(N-1):
  # 현재 교차로 i와 연결된 교차로 개수
  crossway = int(input())
  # i번째에서 갈 수 있는 교차로 번호
  cross_number = list(map(int, input().split()))
  # 교차로 j에 대해 cross에 값 변경해주기
  for j in cross_number:
    #j-1인 이유는 실제 교차로 번호가 2라면 인덱스는 1이기에
    cross[i][j-1] = 1
    
# 플로이드-워셜 알고리즘 ☆☆☆
# 중간 노드(거쳐갈 숫자) 선택 - k를 통해 경로 최적화
for k in range(N):
  # 시작 노드 i
  for i in range(N):
    # 도착 노드 j
    for j in range(N):
      # 직선거리가 있으면 1이 세팅되어서 if문이 불가
      # 직선거리가 없을 경우 여러 중간 노드를 거치면서
      # 최종 j까지 접근이 될때 그 값이 두 노드간 최소거리
      if cross[i][j] > cross[i][k] + cross[k][j]:
        cross[i][j] = cross[i][k] + cross[k][j]

#모든 교차로 순서대로 체크        
for i in range(N):
  #교차로1에서 i까지 연결 경로가 있다면 1이기에 참
  if cross[0][i] < INF:
    #위의 알고리즘 때문에 성립 가능한 조건
    #교차로i에서 자기 자신으로 돌아오는 경로가 있는지 확인
    if 0 < cross[i][i] < INF:
      # 그랬을 경우 cycle은 True
      cycle = True
      break

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

처음 배운 플로이드-위셜 알고리즘으로 풀건데

플로이드-위셜 알고리즘
그래프에서 모든 쌍의 최단 경로를 찾는 알고리즘.
단계별로 중간에 다른 정점을 거쳐가는 모든 쌍의 경로를 최적화

즉 1~3을 가고싶을 때 바로 갈 수 있다면 그게 최단 경로
그러나, 1에서 바로 3을 못간다면 2를 거쳐서 가는게 최단 경로일 수 있다고 가정하면,
그 최단 경로를 구하는 알고리즘이다.
결국 자기 자신 위치까지 올 수 있는 경로를 구하냐 못구하냐의 차이에따라 CYCLE, NO CYCLE을 출력값으로 뽑아올 수 있다는데 아직 처음보는 개념이라 설명을 들었어도 많이 헤깔리긴 한다.

import sys

# 한 줄 씩 읽어오기
input = sys.stdin.readline
# 거리 배열에서 연결 안되어 있을 때 큰 값 설정
# 즉 거리가 엄청 멀리 있다 == 연결 되어 있지 않다
INF = 100000

# 첫 줄 N
N = int(input())
# 사이클 존재 여부 추적 변수
cycle = False

일단 sys로 데이터 뽑아올건데,
처음으로 input을 선언할때 readline 즉 한 줄씩 가져오는 방식으로 사용해봤다.
그리고 INF = 10000으로 세팅해놓은 이유는 두 점간의 거리가 저렇게나 멀다를 표시해준건데, inf로 표현하면 너무 값이 커지므로 적당히 크게 선언,
이렇게 담긴 숫자의 의미는, 두 점간에는 거리가 엄청 떨어져있다, 즉 직접 연결되어있지 않다를 의미하기 위해 큰 숫자를 담아줬다.

N같은 경우 교차로의 개수이므로 바로 int로 뽑아주고,
cycle 즉, 와따리가따리 할 수 있는지 체크를 위해 기본 값 False로 담아준다

# 단순 dfs가 아닌 알고리즘 사용 위해 교차로 간 거리 저장
cross = [[INF for _ in range(N)]for _ in range(N)]

cross는 길을 의미하는 변수,
교차로 간의 거리를 저장하기 위한 리스트 안의 리스트, 2차원 배열이다.
INF를 담아줬기에 모든 교차로는 연결되어있지 않은 상태라고 알고 있으면 된다.

# 마지막 교차로 n이 대피소여서 연결 정보 탐색 필요 x
for i in range(N-1):
  # 현재 교차로 i와 연결된 교차로 개수
  crossway = int(input())
  # i번째에서 갈 수 있는 교차로 번호
  cross_number = list(map(int, input().split()))
  # 교차로 j에 대해 cross에 값 변경해주기
  for j in cross_number:
    # j-1인 이유는 실제 교차로 번호가 2라면 인덱스는 1이기에
    cross[i][j-1] = 1

N-1까지의 범위를 반복문으로 설정한 이유는, 각 교차로를 비교해줄때 N은 마지막 대피소이므로, 교차로 연결 정보 탐색해줄 필요가 없어서 조금이라도 성능 개선을 위해 설정

N이후 입력 값인 crossway는 현재 교차로 i와 연결된 교차로 개수를 의미

cross_number은 그래서 몇번 교차로로 갈 수 있는지 그 숫자가 적혀있으므로, 순서대로 뽑아서 list에 숫자로 담아준다

그다음 뽑은 숫자를 담은 리스트의 길이만큼 for로 반복문을 돌려주면서,

i번째의 번호에서 j-1(인덱스가 하나씩 밀려서 해당 숫자가 위치하므로 ex- 2번은 1인덱스에 담겨있음)의 값을 1로 바꿔버리고
cross에 값을 재할당해준다면,
그 의미는 두 교차로간 이어져있다로 해석할 수 있다
ex- cross[0][1]= 1 <-1번에서 2번으로 가는 교차로가 존재한다

# 플로이드-워셜 알고리즘 ☆☆☆
# 중간 노드(거쳐갈 숫자) 선택 - k를 통해 경로 최적화
for k in range(N):
  # 시작 노드 i
  for i in range(N):
    # 도착 노드 j
    for j in range(N):
      # 직선거리가 있으면 1이 세팅되어서 if문이 불가
      # 직선거리가 없을 경우 여러 중간 노드를 거치면서
      # 최종 j까지 접근이 될때 그 값이 두 노드간 최소거리
      if cross[i][j] > cross[i][k] + cross[k][j]:
        cross[i][j] = cross[i][k] + cross[k][j]

문제를 보고 이걸 떠올리는것 자체가 넌센스, 어렵지만, 그래도 이 코드 자체만 분석하면 이해할 순 있다.
중간 번호 k 안에서 i시작 번호~~ j도착번호까지 3중 반복문(시간 복잡도 n3)을 돌린다면,
해당 if조건에 따라 cross[i][j]의 값을 변경해줄 수 있는데,
저 if문 조건의 의미는 예시를 들어야 좀 더 와닿는다

만약 1에서 3으로 가는 직선 교차로가 있다면??
cross[0][2]= 1일 것이다
그렇다면?
cross[0][2] > cross[0][1] + cross[1][2]
1~2~3이 다 이어져있다고 가정하면
1 > 1 + 1
즉, 직선거리가 중간에 거쳐가는 거리보다 길게 되므로 해당 조건은 충족이 안된다.
그렇다면 저 if문이 충족되려면??
1번호에서 3번호까지의 직선거리가 없었을때
cross[0][2] = 100000 일것이다.
근데 1번호~2번호는 교차로가 있고 2번호~3번호 교차로가 있다면?
cross[0][2] > cross[0][1] + cross[1][2]
10000 > 1 + 1
즉, 직선거리가 없을때 1~2~3 교차로를 이용한게 최단거리이므로
cross[0][2] = 2가 된다.
총 정리하자면,
직선거리가 없다면, 중간 번호를 계속 비교해가며 최종 번호까지 도달해야하는데,
중간 번호에서도 교차로가 이어지지 않는다면, 숫자가 INF가 들어있기에, if문 충족이 안된다.
그렇다면??
이어져있는 교차로들이 있는 합산 숫자가 시작점~도착점까지의 최단거리인 셈이다.

참 이렇게 글로 써도 어렵게 설명되는 내용을 컴퓨터 지식을 가지고 풀어야한다니 어렵다 어려워~~~

# 모든 교차로 순서대로 체크        
for i in range(N):
  # 교차로 1에서 i까지 연결 경로가 있다면 1이기에 참
  if cross[0][i] < INF:
    # 위의 알고리즘 때문에 성립 가능한 조건
    # 교차로 i에서 자기 자신으로 돌아오는 경로가 있는지 확인
    if 0 < cross[i][i] < INF:
      # 그랬을 경우 cycle은 True
      cycle = True
      break

이 부분이 내 기준 매우 중요한 코드인데,
N만큼 for문 실행하면서,
if cross[0][i] < INF:
이 부분 예를들어서,
cross[0][0] 과연 여기에 1이 들어간 교차로가 있을까? 아니다
무조건 INF가 들어있다. 근데 이 조건은 그 밑에 if문에서 다룰텐데 그 전에,
1번에서 3번까지 가는 cross[0][2] 다이렉트 교차로가 없을 경우엔 INF가 담겨있으므로, 조건 성립이 안된다.
다시 말해서,
도착점까지 가는 연결 경로가 있을경우??를 뜻한다
근데 무조건 도착점까지 가게 만들지 않았나? 싶어서 해당 if문을 빼고 실행해봤더니 틀림이 나온다.
즉, 예외적인 부분도 처리를 해줘야 온전한 정답을 얻을 수 있다는 의미
그 아래 if문인 if 0 < cross[i][i] < INF:
여기가 이해가 쉽지 않았는데,

만약 N = 4(4개의 교차로가 있다) 가정해보자

• 교차로 0~1로 연결(직선거리 1)
• 교차로 1~2로 연결(직선거리 1)
• 교차로 2~3로 연결(직선거리 1)
• 교차로 3~1로 연결(직선거리 1)
  

그랬을 경우 이 처럼 교차로로 돌아오는 사이클이 존재하게 된다.

cross[0][1] = 1
cross[1][2] = 1
cross[2][3] = 1
cross[3][1] = 1

코드상으로는 이 인덱스에 1이 담기게 된다.

[[100000,      1, 100000, 100000],
 [100000, 100000,      1, 100000],
 [100000, 100000, 100000,      1],
 [100000,      1, 100000, 100000]]

그리고 실제 배열에선 이렇게 값이 담기게 된다.

실제 플로이드-위셜 알고리즘을 통해 최단 경로를 계산한다면

for k in range(N):
  for i in range(N):
    for j in range(N):
      if cross[i][j] > cross[i][k] + cross[k][j]:
        cross[i][j] = cross[i][k] + cross[k][j]

cross[0][2] > cross[0][k] + cross[k][2]
k가 0이면?
100000 > 100000 + 100000 (성립 안함)
k가 1이면?
100000> 1 + 1(성립함) 즉 cross[0][2] = 2(현재 최소 값)
k가 2이면?
2> 100000 + 100000 (성립 안함)
k가 3이면?
2 > 100000 + 100000(성립 안함)
이런식으로 노가다로 작업을 해본다면

[[100000,      1,      2,      3],
 [100000, 100000,      1,      2],
 [100000,      2, 100000,      1],
 [100000,      1,      2, 100000]]

이러한 값이 나오게 된다.
그렇다면 사이클 코드를 하나하나 넣어서 분석해본다면??

for i in range(N):
  if cross[0][i] < INF:
    if 0 < cross[i][i] < INF:
      cycle = True
      break

i=0이면
cross[0][0]= INF < INF (성립안함)
i=1이면
cross[0][1] = 1 < INF (성립함)
두번째 조건 0 < cross[1][1]= 100000< 100000 (성립 안함)
i=2이면
cross[0][2]=2 < INF (성립함)
두번째 조건 0 < cross[2][2] = 100000< 100000(성립 안함)
i=3이면
cross[0][3]=3 < INF(성립함)
두번째 조건 0 < cross[3][3] = 100000 < 100000(성립 안함)

즉???
사이클이 존재하지 않는다!!
그러나 이 조건을 충족하면 사이클이 존재한다고 생각하면 된다.

이게 참.. 예시를 들어봐도 쉽지 않은 알고리즘은 분명하다!
적어도 내 기준에선..!

cross[i][i] 가 0~INF 사이의 숫자라면 돌아오는 사이클이 있구나 정도를 외우는게 나을 것 같다

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

그렇게 cycle이 있다면 없다면 해당 print 출력...!

하 어렵다 어려워 많이 푼다고 익숙해질 수 있을까..? 하하하핳