백준 2606번 바이러스 어떻게 풀었나.

• 푼 방법

bfs와 dfs를 생각하지 않고 그냥 문제을 읽고 생각나는데로 풀었더니 풀렸다.

기분 째진다

 

그래도 bfs와 dfs를 공부했다.

bfs는 너비우선탐색, dfs는 깊이우선탐색이다.

어떻게 동작하는지는 대충 구글링 해보면 나온다.

 

bfs는 큐를 이용해서 구현했고, dfs는 재귀함수를 이용해서 구현했다.

이 문제에서는 bfs와 dfs 둘중 아무거나 써도 상관이 없지만, 다른 문제를 풀때는 웬지 상관이 있을거 같다.

 

bfs와 dfs를 구현하기 전에 입력을 받아야 하는데, 그 입력은 이차원 리스트 graph를 만들어서 인덱스마다 연결된 노드들을 저장해 주었다.

 

 

---

코드 

내가 직관적으로 푼 코드

import sys
N = int(input())
K = int(input())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(K)]

connect = {1}

for _ in range(N):
	for a in A:
		for i in a:
			if i in connect:
				connect.add(a[0])
				connect.add(a[1])
				break

print(len(connect)-1)

bfs

import sys
from collections import deque
N = int(input())
K = int(input())

graph = [[] for _ in range(N+1)]
visit = [0]*(N+1)

for _ in range(K):
	a, b = map(int, sys.stdin.readline().split())
	graph[a].append(b)
	graph[b].append(a)

visit[1] = 1
Q = deque([1])

while Q:
	t = Q.popleft()
	for i in graph[t]:
		if visit[i] == 0:
			Q.append(i)
			visit[i] = 1

print(sum(visit)-1)

dfs

import sys
from collections import deque
N = int(input())
K = int(input())

graph = [[] for _ in range(N+1)]
visit = [0]*(N+1)

for _ in range(K):
	a, b = map(int, sys.stdin.readline().split())
	graph[a].append(b)
	graph[b].append(a)

def dfs(i):
	visit[i] = 1
	for j in graph[i]:
		if visit[j] == 0:
			dfs(j)

dfs(1)

print(sum(visit)-1)