https://school.programmers.co.kr/learn/courses/30/lessons/43162
해당 문제는 뭉텅이의 개수를 세는 것이라고 이해하면 된다.
위의 그림에서 보면 1번과 2번이 연결되어 있기 때문에 한 뭉텅이로 보고, 3번을 독립적인 뭉텅이로 보아, 총 2개의 뭉텅이가 있다고 볼 수 있다.
뭉텅이 관련 문제는, 각각의 노드와 연결된 모든 노드를 탐색한 후 True 값을 리턴해서 뭉텅이의 개수를 한 개씩 카운트 하는 방식을 구현할 수 있다.
우선 나는 DFS 알고리즘을 통해 해당 문제를 해결헀다.
from collections import deque
def dfs(graph, node, visited):
if not visited[node]:
visited[node] = True
for i in graph[node]:
if not visited[i]:
dfs(graph, i, visited)
return True # 방문 안했으면 일단 뭉텅이 취급
return False
def bfs(graph, start_node, visited):
q = deque([start_node])
if not visited[start_node]:
visited[start_node] = True
while q:
v = q.popleft()
for i in graph[v]:
if not visited[i]:
q.append(i)
visited[i] = True
return True
return False
def solution(n, computers):
graph = [set() for _ in range(n+1)]
visited = [False] * (n+1)
for i in range(n):
for j in range(n):
if computers[i][j] == 1 and i != j:
graph[i+1].add(j+1)
graph[j+1].add(i+1)
count = 0
for i in range(1, n+1):
if dfs(graph, i, visited):
# if bfs(graph, i, visited):
count += 1
print(count)
return count우선 dfs 함수의 로직을 살펴보자.
해당 함수가 False와 True를 리턴하는 상황의 차이에 대해서 알아보면 되는데, 우선 함수는 방문하지 않은 노드라면 방문값을 True로 바꾸는 핵심 로직을 갖고 있다.
이는 dfs가 call 될 때 가장 먼저 처리하는 로직이다.
dfs는 동작 원리가, 스택에 삽입하고 방문처리를 하는 것으로, 함수 콜 이후에 바로 핵심 로직을 실행하면 된다.
따라서 1번에 관련해서 dfs가 콜이 되었다면, 연결된 모든 노드의 방문 처리가 완료될 것이다.
따라서 후에 2번에 관련해서 dfs가 콜이 된다면, 2번은 이미 방문처리가 되어있어 False 값을 리턴하고 뭉텅이의 카운트에 들어가지 않게 되는 것이다.
다음은 bfs 함수이다.
bfs함수에서도 핵심 로직 처리는 dfs와 같다.
방문처리가 된 것인지 확인하고, 방문처리 된 것이 아니라면 일단 count, 아니라면 False 리턴.
다만 bfs는 큐 자료구조를 이용한다.
그래서 핵심로직을 처리하는 위치가 큐에 삽입 이후이다.
어렵지 않게 푼 문제였다!
