[백준/Python] 2606번 바이러스 (DFS,BFS,유니온파인드)

문제 설명

---

 

---

문제 풀이

---

1번 컴퓨터와 연결된 컴퓨터의 갯수를 구하는 문제입니다.
총 3가지 방법의 풀이로 문제를 해결할 수 있습니다.

1. BFS(너비우선탐색): 1번 컴퓨터와 연결된 가장 맨허튼 거리가 가까운 컴퓨터부터 갯수 파악
2. DFS(깊이우선탐색): 1번 컴퓨터와 연결된 컴퓨터의 마지막 연결점을 우선적으로 다녀오며 연결 갯수 파악
3. 유니온파인드: 부모를 기준으로 묶어진 집합의 원소 갯수를 파악

이 문제에서는 방향이 중요하지 않으므로 undirected graph(방향이 없는 그래프)로 만들기 위해 양방향 모두 연결처리 해주었습니다.
1번 BFS풀이의 경우 array list 형식으로 100개의 모든 배열을 생성하는 방법을 사용해서 풀어냈고

2번 DFS풀이의 경우 linked list 형식으로 연결된 노드만 추가하는 방법을 사용해서 풀어냈습니다.

 

---

코   드

---

너비우선탐색(BFS) + 배열(array list) 풀이

import sys

N = int(sys.stdin.readline())
connectLength = int(sys.stdin.readline())
computers = [[False for _ in range(N+1)] for _ in range(N+1)]
visited = [False for i in range(N+1)]
visited[1] = True

def findVirus(node):
    que = [1]
    cnt = 0
    
    while len(que):
        front = que.pop(0)
        for idx, connected in enumerate(computers[front]):
            if connected and not visited[idx]:
                visited[idx] = True
                que.append(idx)
                cnt+=1
    return cnt          

for connect in range(connectLength):
    lhs, rhs = map(int, sys.stdin.readline().split())
    computers[lhs][rhs] = True
    computers[rhs][lhs] = True

print(findVirus(1))

 

깊이우선탐색(DFS) + 리스트(linked list) 풀이

import sys

N = int(sys.stdin.readline())
connectLength = int(sys.stdin.readline())
computers = [[] for i in range(N+1)]
visited = [False for i in range(N+1)]
visited[1] = True

def findVirus(node):
    cnt = 0
    for computer in computers[node]:
        if not visited[computer]:
            visited[computer] = True
            cnt += findVirus(computer) + 1
    return cnt

for connect in range(connectLength):
    lhs, rhs = map(int, sys.stdin.readline().split())
    computers[lhs].append(rhs)
    computers[rhs].append(lhs)

print(findVirus(1))

 

유니온파인드(Union Find) 풀이

import sys
N = int(sys.stdin.readline())
parents = [i for i in range(N+1)]

def find(child):
    if child == parents[child]:
        return child
    return find(parents[child])

def union(lhs, rhs):
    l = find(lhs)
    r = find(rhs)
    
    if l == r:
        return
    elif l > r:
        parents[l] = r
    else:
        parents[r] = l

netLength = int(sys.stdin.readline())
for i in range(netLength):
    lhs, rhs = map(int,sys.stdin.readline().split())
    union(lhs, rhs)

cnt = 0
for item in parents:
    if find(item) == 1:
        cnt+=1
print(cnt - 1)

---

느낀점: 머리속에 다른 풀이가 있는 상태에서 다른 풀이를 구현하려니 시간이 오래걸렸는데, 하나의 풀이만 생각하지 않고 뭐가 더 효율적인지 고민할 수 있는 머리가 되면 좋겠다.

링크: https://www.acmicpc.net/problem/2606

2606번: 바이러스