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

3주차 | 문제 4. 순환하는 수로

문제

구름이는 도시의 물을 관리하는 관리자이다. 현재 도시에는 물을 잠시 보관하는 물탱크와 물탱크끼리 연결하는 수로가 아래의 조건으로 설치되어 있다.

• N개의 물탱크와 N개의 수로가 있다.
• 물탱크는 1번부터 N번까지 있다.
• 수로가 연결된 물탱크는 양 쪽으로 물이 흐른다.
• 서로 다른 두 물탱크를 잇는 수로는 최대 하나이다.
• 물탱크에서 연결된 물탱크는 항상 다른 물탱크이다.

도시의 물은 흐르지 않으면 녹조류가 생기기 때문에, 항상 물이 순환하도록 유지하는 것이 중요하다.

하지만, 구름이는 순환하는 물이 항상 모든 물탱크를 지나지 않는다는 점을 확인했다. 구름이는 현재 상태의 수로를 확인하고, 순환하는 수로를 찾기로 한다. 이때 순환하는 수로란, 물탱크의 물이 아래의 조건을 만족하면서 끊임없이 순환해야 한다.

• 모든 물탱크에는 물이 없는 상태에서 시작한다.
• 최초의 하나의 물탱크를 선택하여, 물을 채우고 물탱크에 연결된 다른 물탱크에 물을 공급한다.
• 다른 물탱크에 물을 공급하는 물탱크는 물이 모두 비워질 때까지, 다른 물탱크에 공급한다.
• 순환하는 수로의 정의를 다음과 같이 정의하자. 어떤 물탱크에 있던 물이 특정한 수로들을 거쳐 다시 원래의 물탱크로 돌아올 때, 그 수로들의 집합을 순환하는 수로라 한다.
• 순환하는 수로의 집합의 크기는 최소 3개 이상이어야 한다.

아래의 예시를 들어보자.

위의 예시에서 최초로 1번 물탱크에 물을 채우고, 다른 물탱크에 공급을 시작한다.

1번 물탱크에 연결되어 있는 다른 모든 물탱크에 물이 공급된다. 2번 물탱크에 물이 공급이 되면, 2번 물탱크는 물을 공급해준 1번 물탱크를 제외하고 3, 4번 물탱크에 물을 공급한다.

3번 물탱크의 물 흐름은 {3 > 4 > 2}, {5 > 3 > 4} 를 거친다. 5번 물탱크로 간 물은 다시 물을 공급해준 4번 물탱크로 올 수 없으며, 2번 물탱크는 물을 공급해준 4번과 1번 물탱크로 물을 공급할 수 없다.4번 물 탱크의 물 흐름은 {4 > 2}, {5 > 3  > 4 > 3} 을 거친다.

물은 조건에 따라 흐르기 때문에, {2 > 3 > 4} 물 탱크만 흐르게 된다. 이를 보고 순환하는 수로라고 한다.

구름이가 도시의 물 탱크의 개수와 수로의 상태가 주어졌을 때, 가장 큰 순환하는 수로를 찾고, 수로의 집합의 크기와 번호를 오름차순으로 출력하시오. (단, 항상 순환하는 수로가 존재한다)

입력

첫째 줄에는 물탱크의 수와 수로의 수를 나타내는 수 N(5≤N≤10,000)이 주어진다.

둘째 줄부터 각 줄에는 수로의 연결 상태를 의미하는 두 수가 a b(1≤a,b≤N)의 형태로 한 줄에 하나씩 주어진다. a번 물탱크와 b번 물탱크를 연결하는 수로가 있음을 의미한다.

출력

첫째 줄에는 구름이가 발견한 순환하는 수로에 포함된 물탱크의 수를 출력한다.둘째 줄에는 순환하는 수로를 구성하는 물탱크의 번호를 오름차순으로 공백으로 구분하여 출력한다.

---

문제 3과 마찬가지로 구름 해설을 토대로 이해한 바를 정리하는 내용으로 작성되어 명확하지 않을 수 있음을 미리 알립니다.

defaultdict를 이용하여 양방향 그래프 만들기

문제 4 또한 양방향 그래프를 이용하는 문제이므로 문제 3과 같은 방식으로 양방향 그래프를 만든다.

import sys
input = sys.stdin.readline
from collections import defaultdict

n = int(input())
graph = defaultdict(list)
for i in range(n):
    s, e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)

 

깊이 우선 탐색; DFS(Depth-First Search)

이 문제에서는 깊이 우선 탐색을 활용하여 해결할 수 있다.  깊이 우선탐색은 다음과 같은 특징을 가진다.

• 깊이 우선 탐색; 하나의 경로가 끝날 때까지 탐색하는 방법
• BFS와는 다르게, 하나의 경로를 우선적으로 끝까지 탐색해야 하기 때문에 다음에 탐색할 노드 중 가장 최근에 추가된 노드를 우선적으로 방문해야 함

문제에서 주어진 조건 중 아래 두가지를 살펴보면 하나의 경로를 완료한 후에 다른 경로를 선택해야 함을 미루어 짐작할 수 있어 이 문제는 DFS를 통해 해결할 수 있다.

• 최초의 하나의 물탱크를 선택하여, 물을 채우고 물탱크에 연결된 다른 물탱크에 물을 공급한다.
• 다른 물탱크에 물을 공급하는 물탱크는 물이 모두 비워질 때까지, 다른 물탱크에 공급한다.

DFS 구현은 가장 최근에 추가한 노드를 우선적으로 탐색해야 하므로, 후입선출(LIFO)의 특징을 가진 자료 구조인 스택(Stack)을 이용한다. 스택 자료구조는 제공되지 않기 때문에 리스트를 통해 쉽게 구현할 수 있다.

s = [] # 스택 s
s.append(0) # 0번 노드부터 시작한다고 가정
while s:
    # deque에서는 popleft() 사용
    cur = s.pop() 
    print("현재 위치는 %d 입니다."%(cur))

    for i in graph[cur]:
        if visited[i] == 0: 	# 한번도 방문한 적이 없으면, visited+1하고 q에 추가한다
            visited[i] = 1
            s.append(i)

• 스택 s에 시작 노드인 0번 노드를 추가한다.
• s가 비어있지 않으면 while문을 계속해서 진행한다.
• s의 맨 뒤에 위치하는 값을 가져와 현재 위치(cur)로 지정한다.
• 현재 위치한 노드와 연결된 노드 정보를 graph에서 가져온다. 가져온 노드(i)가 방문한 적이 없는 노드이면 visited값을 +1해주고 s에 추가한다.

재귀 함수 구현

문제에서 주어진 5개의 조건에 모두 만족함과 동시에 그래프 내에서 사이클을 찾기 위해서는 재귀 함수를 사용해야 한다.

재귀 함수에서 사용하는 3가지 변수는 다음과 같다.

Visited

• 방문 여부를 판단
• -1이면 방문한 적이 없다. 1이면 방문한 적이 있다. 

Finded

• 기본 값은 -2이며, 직전에 방문했던 방문 지점의 노드 번호를 저장
• 만약에 탐색 중에 Finded 값이 노드 번호와 같다면, 탐색 종료와 함께 -2로 바꿔줌 → (이미 탐색했거나, 이동할 수 없는 경로이기 때문에)

Circle

• 조건에 따라서, 탐색하고 있는 값들을 추가

재귀 정지 조건은 다음과 같으며, 정지 조건이 없다면 새로운 탐색 재귀를 불러온다.

• 도착한 노드가 출발한 노드일 경우 값을 반환하고 정지.
• 더 이상 탐색할 노드, 즉 이동할 경로가 없을 경우 탐색을 정지.
• 물을 공급해준 노드일 경우 탐색을 정지.

구름 정답 코드

import sys
sys.setrecursionlimit(10**8) # 재귀 깊이 제한
from collections import defaultdict

n=int(sys.stdin.readline()) # 물탱크의 수=수로의 수

graph=defaultdict(list) # 연결된 수로들의 정보를 저장하는 defaultdict
for _ in range(n):
	a,b=map(int,sys.stdin.readline().split()) # 연결된 두 수로
	graph[a].append(b)
	graph[b].append(a)

# 변수 선언
#1번~n번섬 인덱싱을 편리하기 위해 n+1개로 생성
visited=[0 for _ in range(n+1)] # 방문 기록/-1 없다, 1 있다
finded=-1 # 직전에 방문한 노드 번호 저장/기본값 -2
circle=[] # 탐색하고 있는 노드 저장

# 탐색 재귀 함수
def FindCycle(u,tar): # u(출발)에서 tar(도착)로 오는 과정에 사이클이 존재하는지 판단하는 함수
	global finded # 위에서 선언한 finded를 사용하기 위해 전역변수 사용 명시
	
	if visited[u]==1: # 방문 기록이 있으면(1이면)
		finded=u # 방문 노드를 u로 
		if u not in circle: # 탐색 노드에 u가 없으면 추가
			circle.append(u)
		return
	
	visited[u]=1 # 방문 기록 없으면 1로 바꿔줌
	
	for i in graph[u]: # u와 연결된 노드가
		if i==tar: # 도착 노드와 같으면
			continue
		FindCycle(i,u) # 그렇지 않으면 i를 새로운 탐색 지점으로 시작하여 u까지의 사이클을 찾는다
		if finded==-2: # 이미 탐색했거나, 이동할 수 없는 경로이면(기본값 -2) 종료
			return
		if finded==u: # 방문노드가 u이면 이미 방문한 것이므로 종료
			finded=-2
			return
		if finded>=0: # 새로운 방문 노드일 때 탐색 노드에 없으면 추가하고 종료
			if u not in circle:
				circle.append(u)
			return

FindCycle(1,1)

print(len(circle)) # 물탱크의 수 출력

circle.sort() # 오름 차순으로 정렬 후, 공백으로 구분해 출력
for i in circle:
	print(i, end=' ')