9월의 마지막 날, 전라남도 완도에서 이 글을 작성하고 있다.
원래는 내일 오후에 농구 대회를 위해 내려올 예정이었는데, 오전에 LINE 직무테스트가 잡혀서 그냥 하루 일찍 내려왔다. 오션뷰가 아주 멋진 카페에서 혼자만의 시간을 가지며 알고리즘 문제도 풀고 CS 공부도 하다가, 오랜만에 개발일지를 남겨본다 😊
알고리즘
오늘은 프로그래머스에서 네트워크라는 문제를 풀어보았다.
레벨 3짜리 문제인데, 다음과 같이 생겼다.
문제에 따르면 i번 컴퓨터와 j번 컴퓨터가 연결되어 있다면 computers[i][j] == 1 을 갖는 인접행렬이 주어져 있다. 다음 주에 있을 코딩테스트를 대비할 겸 BFS, DFS, 그리고 Union-Find로 각각 풀어보았다.
BFS 풀이
첫 번째 컴퓨터부터 살펴보며, 인접한 컴퓨터부터 너비에 따라 탐색해가게 된다. 
가령 그림과 같이 0번 컴퓨터와 2번 및 3번 컴퓨터가 연결되어 있다면, 2번과 3번 컴퓨터를 방문처리(visited = True) 해주며 네트워크에 편입시킨다. 그리고 2번 컴퓨터와 연결된 컴퓨터들을, 이후엔 3번 컴퓨터와 연결된 컴퓨터들을 순차적으로 탐색해준다.
from collections import deque
def solution(n, computers):
visited = [False] * n
cnt = 0
for i in range(n):
if visited[i]: continue
cnt += 1
visited[i] = True
q = deque([i])
while q:
now = q.popleft()
for j, connected in enumerate(computers[now]):
if not visited[j] and connected:
visited[j] = True
q.append(j)
return cnt수행시간은 다음과 같다. 인접행렬을 사용한 그래프의 경우 O(N²)의 시간복잡도를 가진다고 알고 있는데, 생각보단 빠르다.
그래서 글을 작성하던 중 호기심이 생겨서 문제에서 제공한 인접행렬을 바탕으로 만든 인접리스트를 구성하고, 인접리스트를 사용하는 BFS도 추가적으로 구현해보았다.
from collections import deque, defaultdict
def solution(n, computers):
graph = defaultdict(list)
for i in range(n):
for j, connected in enumerate(computers[i]):
if i!=j and connected:
graph[i].append(j)
visited = [False] * n
cnt = 0
for i in range(n):
if visited[i]: continue
cnt += 1
visited[i] = True
q = deque([i])
while q:
now_pc = q.popleft()
for next_pc in graph[now_pc]:
if visited[next_pc]: continue
visited[next_pc] = True
q.append(next_pc)
return cnt
비교해보니, 특별히 차이나진 않는다. 생각해보니 인접리스트가 처음부터 주어진게 아니다보니까, 인접행렬 전체를 탐색해야 인접리스트를 만들 수 있다. 그래서 별 차이 없는듯🙃
DFS 풀이
인접한 컴퓨터들부터 순차적으로 탐색하는 BFS와 달리, DFS는 더 이상 dfs 함수를 호출할 수 없을 때까지 연산을 수행한다. 달리 말하자면 더 이상 깊게 들어갈 수 없을 때까지 처리한다는 것이다. 
BFS와 동일한 그림이지만 0번 컴퓨터에서 2번 컴퓨터를 방문하고 나서, 0번에 인접한 또다른 컴퓨터(3번)가 아니라, 2번 컴퓨터에 인접한 컴퓨터(4번)를 탐색하게 된다는 것이다.
from collections import deque
def solution(n, computers):
visited = [False] * n
cnt = 0
def dfs(x):
if visited[x]: return 0
visited[x] = True
for y in range(n):
if computers[x][y] == 1 and not visited[y]:
dfs(y)
return 1
for computer in range(n):
cnt += dfs(computer)
return cnt수행시간을 봤을 때, 어떤 테스트에서는 DFS가 빠르지만 어떤 테스트에서는 BFS가 더 빠르다. 역시나 주어진 입출력에 따라서 달라지는 부분인듯 하다. 
Union-Find 풀이
마지막으로 Union-Find 풀이로도 가능하다.
인접행렬 전체를 딱 한번 탐색하면 네트워크의 갯수를 파악할 수 있다.
def solution(n, computers):
def find(N):
if N != parent[N]:
parent[N] = find(parent[N])
return parent[N]
def union(A,B):
v1, v2 = find(A), find(B)
if v1 != v2:
if v1 > v2:
v1, v2 = v2, v1
parent[v2] = v1
parent = [i for i in range(n)]
for i in range(n):
for j in range(n):
if i == j: continue
if computers[i][j] == 1:
union(i,j)
for i in range(n):
find(i)
return len(set(parent))