[구름 알고리즘 먼데이 챌린지] 3주차 4번 순환하는 수로

---

 

22/11/07

 

 

DFS/BFS 문제로, 사이클을 출력하는 문제이다.

---

 

문제 접근 방식:

 

 

사실 이 문제의 해설보다 더 간단한 방법으로 나는 풀었다.

 

심지어 BFS, DFS도 돌리지 않았다.

 

나는 문제 조건의 핵심을 꿰뚫어봤다. 먼저, 문제 조건을 보면, 사이클은 단 하나만 존재한다고 했다.

 

때문에, 노드들과 간선들이 주어져 있으면, 노드들 중에 간선이 하나만 연결되어 있는 노드들은 사이클을 이루고 있지 않다고 생각했다.

 

왜냐하면, 그 노드가 사이클에 포함되어있다면, 그 노드는 최소 2개 이상의 간선에 연결되어 있기 때문이다.

 

 

이러한 이유로, 사이클을 이루고 있지 않은 노드는 그 간선과 노드를 그래프에서 제거해버렸다.

 

이 과정을 계속 반복하다보면 결국 사이클 하나만 남게 되는데, 이것을 오름차순으로 출력하면 끝.

 

간단하다.

 

문제 해설보다 개인적으로 이 풀이가 더 간단하다고 생각한다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 알고리즘 먼데이 챌린지 3주차 4번 문제
# 그래프
import sys
input = sys.stdin.readline

N = int(input())
graph = [[] for _ in range(N+1)]
edges = [0 for _ in range(N+1)]
cycle = []
for _ in range(N):
    u, v = map(int, input().rstrip().split())
    graph[u].append(v)
    graph[v].append(u)
    edges[u] += 1
    edges[v] += 1

flag = False
while True:
    if flag:
        break
    else:
        flag = True
        for i in range(1, N+1):
            if edges[i] == 1:
                j = graph[i][0]
                graph[i] = 0
                graph[j].remove(i)
                edges[i] -= 1
                edges[j] -= 1
                flag = False
                break

for i in range(1, N+1):
    if edges[i] > 0:
        cycle.append(i)
print(len(cycle))
print(*cycle)