알고리즘 유형 : 트리
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/4803
SOLVE 1
BFS 풀이
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
# start 노드부터 시작하여 BFS를 끝까지 돌고
# 사이클 존재 여부를 리턴하는 함수
def findCycle(start):
isCycle = False
q = deque()
q.append(start)
while q:
cnt_node = q.popleft()
# 노드를 큐에서 뽑았을 때 visited를 갱신해줌.
# 이 때, 뽑은 노드의 visited가 이미 1인 경우는
# 사이클이 존재한다는 것을 의미함
# 예를 들어, 1-2, 2-3, 3-1인 사이클이 있다고 생각해보자.
# 1에서 2와 3을 큐에 넣고 1의 visited는 1이 된다.
# 그 다음 2를 큐에서 뽑고, visited를 1로 한 다음
# 3을 큐에 넣는다(아직 1에서 넣은 3이 뽑기 전이므로 visited가 0)
# 그 다음 1에서 넣은 3을 큐에서 뽑고 visited에 1을 넣는다.
# 이제 큐에는 2에서 넣은 3이 아직 남아있다. 이 것을 뽑았을 때
# visited[3]이 이미 1이므로 사이클로 판정
if visited[cnt_node]:
isCycle = True
visited[cnt_node] = 1
for adj_node in graph[cnt_node]:
if visited[adj_node] == 0:
q.append(adj_node)
return isCycle
n, m = map(int, input().split())
case = 1
while n != 0 or m != 0:
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)
count = 0
# 양방향 매핑
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
# visited가 0인 모든 노드를 돌면서
# 가능한 모든 연결 요소(연결 그래프)를 순회함
for node in range(1, n+1):
if visited[node] == 0:
if not findCycle(node):
count += 1
if count == 0:
print(f'Case {case}: No trees.')
elif count == 1:
print(f'Case {case}: There is one tree.')
else:
print(f'Case {case}: A forest of {count} trees.')
case += 1
n, m = map(int, input().split())SOLVE 2
DFS 풀이
import sys
input = sys.stdin.readline
# start 노드부터 시작하여 DFS를 끝까지 돌고
# 사이클 존재 여부를 리턴하는 함수
def findCycle(start):
for adj_node in graph[start]:
# 인접 노드가 자신의 부모 노드인 경우 패스
if parent[start] == adj_node:
continue
# 인접 노드가 부모 노드가 아닌데 방문 이력이
# 있다는 것은 곧 사이클을 의미함
if visited[adj_node]:
return True
parent[adj_node] = start
visited[adj_node] = 1
# 인접 노드를 루트 노드로 하는 서브트리에
# 사이클이 존재하면 곧 전체 트리에 사이클이
# 존재하는 것과 같음
if findCycle(adj_node):
return True
return False
n, m = map(int, input().split())
case = 1
while n != 0 or m != 0:
graph = [[] for _ in range(n+1)]
parent = [-1]*(n+1)
visited = [0]*(n+1)
count = 0
# 양방향 매핑
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
# visited가 0인 모든 노드를 돌면서
# 가능한 모든 연결 요소(연결 그래프)를 순회함
for node in range(1, n+1):
if visited[node] == 0:
parent[node] = node
visited[node] = 1
if not findCycle(node):
count += 1
if count == 0:
print(f'Case {case}: No trees.')
elif count == 1:
print(f'Case {case}: There is one tree.')
else:
print(f'Case {case}: A forest of {count} trees.')
case += 1
n, m = map(int, input().split()) SOLVE 1) 풀이 요약 (BFS 풀이)
-
전체적인 수행을 테스트 케이스의 첫 번째 케이스로 예를 들어 설명하면 다음과 같다.
1에서부터 BFS를 돌고 사이클을 판정한다.(사이클이 없는 경우 정답 카운팅) > 2는 1에서 BFS를 돌 때 방문했었다. > 3도 > 4도 > 5는 아직 미방문이므로 5로부터 BFS 돌기 > 5는 단일 루트 노드 트리이므로 정답 카운팅 > 6도 카운팅 > 트리는 3개임
-
사이클을 구하기 위해 기존의 익숙한 BFS 형태와는 약간 다른 BFS를 작성할 것이다.
사이클을 판정할 수 있는 BFS 로직은 다음과 같다.
1) visited는 노드를 큐에 넣을 때 갱신하는 것이 아니라, 큐에서
뽑을 때갱신해준다. 즉, 큐에서 뽑을 때까지 그 노드는 중복으로 큐에 여러 개가 들어갈 수도 있는 것이다.2) 문제의 세 번째 테스트 케이스를 예로 들어보면, 1-2, 2-3, 3-1 사이클이 있는데,
처음에 큐에 1을 넣는다. 이 후 1을 뽑으면서 visited[1] = 1을 해주고, 인접 노드인 2와 3을 큐에 넣어준다.
그 다음 2를 큐에서 뽑아주고 visited[2] = 1을 해준다. 인접 노드인 1과 3중, 1은 visited가 1이지만 3은 아직 visited가 0이므로 큐에 넣어준다.
그 다음 1을 뽑을 때 넣어줬던 3을 큐에서 뽑아준 후 visited[3] = 1을 해준다. 이 3의 인접노드 1, 2는 이미 visited가 1이므로 아무것도 큐에 넣지 않는다.
이제 큐에는 2를 뽑을 때 넣어줬던 3만 남았다. 이 것을 뽑고나서 visited를 확인해본다. 이미 visited가 1이 되어있는데, 이 것은 사이클이 존재함을 의미한다.
-
이 BFS를 1부터 n까지 모든 노드를 돌아주면 되는데, 다만 주의할 점이 있다.
첫 번째 테스트 케이스를 예로 들면, 1에서 BFS를 돌면 1부터 4까지의 노드의 visited가 1이 되므로, 이 들은 BFS를 더 돌릴 필요가 없다. 즉, 1부터 n까지 순회하면서 visited가 0인 노드만 BFS를 돌려주면 된다.
- BFS의 반환 값은 사이클 여부이다. 사이클을 의미하는 True라면 count에 1을 더해준다. 최종적으로 count는 그래프에서의 트리의 개수를 의미한다.
SOLVE 2 풀이 요약 (DFS 풀이)
-
DFS 풀이에서는 리스트를 두 개 활용한다. 하나는 visited 리스트, 하나는 parent 리스트이다.
parent[n] = v 는 n의 부모 노드가 v임을 의미한다.
visited[n]은 1이면 기방문, 0이면 미방문을 의미한다.
-
1부터 n까지 visited가 0인 노드에 한해 DFS를 각각 돌려준다.
이 DFS는 start 노드가 포함된 연결 그래프(연결 요소)를 모두 순회하면서 사이클이 있는지를 판단한다.
DFS 로직을 살펴보면, 현 노드에 대해 인접 노드를 순회하면서 parent와 visited를 갱신하고 재귀를 호출한다.
단, 이를 수행하기 전에 먼저 if로 검사할 것이 있는데, 우선 인접 노드가 자신의 부모 노드와 같은 경우는 이미 방문한 노드이므로 continue 해준다.
그리고 부모 노드가 아니면서 visited가 1인 경우가 핵심인데, 이는 곧 사이클임을 의미한다.
DFS를 부모-자식 방향으로 순회하고 있는데, 트리에서 자식 노드에서 그 인접 노드로 방문하고자할 때, visited가 1인 경우는 부모 노드인 경우밖에 없다. 즉, 이는 곧 사이클임을 의미하는 것이다.
만약 이 경우도 아니라면, 인접 노드의 parent와 visited를 갱신하고 재귀를 호출해준다. 인접 노드를 루트 노드로 하는 서브트리에 사이클이 존재하면, 즉 재귀 함수의 리턴값이 True이면 전체 트리 또한 사이클이 존재하는 그래프가 된다.
배운 점, 어려웠던 점
-
그래프에서 사이클을 찾는 방법을 몰라서 검색해봤다.
BFS와 DFS로 한 연결 요소를 모두 돌고, 그 것에 사이클이 존재하는지를 판단하는, 즉 탐색한 부분 그래프가 트리인지를 판단하는 로직을 배웠다.
-
DFS 풀이에서, 인접 노드에 대해 DFS를 재귀적으로 호출할 때, 사이클이 판정되는 경우 True를 리턴하고 함수를 종료시키는데, 이 경우
그 외의 다른 인접 노드에 대한 부분 그래프를 다 못돌지 않나? 그럼 부분 연결 그래프의 모든 노드의 visited가 다 1이 되지 못해서 한 연결 그래프를 두번 나눠서 DFS를 돌리게 되버리는 경우가 생기지 않나?라는 의문점이 들었다.결과적으로는 AC를 받긴 했는데, 저 의문점은 아직 해결이 안됐다. 나중에 다시 한 번 공부해보면서 꼭 이해해봐야겠다...
