[백준 파이썬] 11581 구호물자

 

11581번: 구호물자

문제

그래프에서 시작 정점으로 다시 돌아오는 경우를 판단하는 문제이다.

---

 

아이디어

DFS를 이용해서 방문여부를 판단하며 문제를 풀 수 있을거라 생각했다.

하지만 플로이드를 연습할 겸 플로이드 워셜로 문제를 풀어보았다.

 

플로이드 워셜은 모든 정점의 경로를 탐색하기때문에 시작지점으로 다시 돌아올 경우를 판단할 수 있다.

---

풀이

N = int(input())

graph = [[0] * (N+1) for _ in range(N+1)]

for i in range(1, N):
  temp = int(input())
  a = list(map(int, input().split()))

  for j in a:
    graph[i][j] = 1

 

그래프의 기본 정보를 입력해준다.

처음 정보가 입력된 그래프에는 연결된 간선의 정보가 들어있다.

for k in range(1, N+1):
  for i in range(1, N+1):
    for j in range(1, N+1):
      if graph[i][k] and graph[k][j]:
        graph[i][j] = 1

그 후 플로이드 워셜을 사용한다.

이 때 만약 i와 j가 같고 

graph[i][k] 값과 graph[k][j] 값이 모두 1일경우 

한 정점을 지나 다시 돌아온다는 의미이므로 자기자신에 대한 경로를 1로 초기화한다.

 

for i in range(1, N+1):
  if graph[1][i] == 1 and graph[i][i] == 1:
    ans = "CYCLE"

 

Cycle을 판단하기 위해 그래프를 탐색한다.

자기자신에 대한 경로가 1일경우 위에서와 같이 다른 정점으로 갔다 다시 돌아왔다는 의미이므로 순환이 된것이다.

또한 시작지점에서 다시 시작지점으로 돌아와야하므로 시작지점과 연결되어있는지 판단한다.

 

---

코드

N = int(input())

graph = [[0] * (N+1) for _ in range(N+1)]

for i in range(1, N):
  temp = int(input())
  a = list(map(int, input().split()))

  for j in a:
    graph[i][j] = 1




for k in range(1, N+1):
  for i in range(1, N+1):
    for j in range(1, N+1):
      if graph[i][k] and graph[k][j]:
        graph[i][j] = 1


ans = "NO CYCLE"

for i in range(1, N+1):
  if graph[1][i] == 1 and graph[i][i] == 1:
    ans = "CYCLE"

print(ans)