백준 2606번. 바이러스

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

2606번: 바이러스

BFS 사용(48ms)

# 1번과 연결되어 있는 컴 수 출력하기
def bfs(arr,start):
    global cnt
    visited = [0] * (n+1)
    q = []
    q.append(start)
    while q:
        t = q.pop(0)
        if not visited[t]:
            visited[t] = 1
            cnt += 1
            for i in arr[t]:
                if not visited[i]:
                    q.append(i)


n = int(input()) # 컴퓨터 수
pair = int(input()) # 직접 연결된 컴퓨터 쌍의 수
arr = [[] for _ in range(n+1)]
cnt = 0
for _ in range(pair):
    com1, com2 = map(int,input().split())
    arr[com1].append(com2)
    arr[com2].append(com1)  # [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]
bfs(arr,1)
print(cnt-1)

재귀 DFS 사용(56ms)

def dfs(start):
    visited[start] = 1
    for w in range(1,n+1):
        if arr[start][w] == 1 and visited[w] == 0:
            dfs(w)

n = int(input())
pair = int(input())
arr = [[0]*(n+1) for _ in range(n+1)]
visited = [0] * (n+1)
cnt = 0
for _ in range(pair):
    com1, com2 = map(int,input().split())
    arr[com1][com2] = 1
    arr[com2][com1] = 1
dfs(1)
for i in range(2,n+1):
    if visited[i]:
        cnt += 1
print(cnt)

재귀가 아닌 DFS 사용(48ms)

def dfs(start):
    global cnt
    stack = []
    visited[start] = 1
    while True:
        for w in range(1, n+1):
            if arr[start][w] == 1 and visited[w] == 0:
                stack.append(start)
                start = w
                cnt += 1
                visited[start] = 1
                break
        else:
            if stack:
                start = stack.pop()
            else:
                break

n = int(input())
pair = int(input())
arr = [[0]*(n+1) for _ in range(n+1)]
visited = [0] * (n+1)
cnt = 0
for _ in range(pair):
    com1, com2 = map(int,input().split())
    arr[com1][com2] = 1
    arr[com2][com1] = 1
dfs(1)
print(cnt)

+24.10.28 재귀 BFS 사용

n = int(input())
m = int(input())
visited = [0] * (n+1)
arr = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)

def recur(node):
    visited[node] = 1
    for i in arr[node]:
        if visited[i] == 1:
            continue
        recur(i)

recur(1)
print(sum(visited)-1)

+24.10.28 재귀 DFS 사용

from collections import deque

n = int(input())
m = int(input())
visited = [0] * (n+1)
arr = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)

q = deque()
q.append(1)

while q:
    node = q.popleft()
    visited[node] = 1

    for i in arr[node]:
        if visited[i] == 1:
            continue
        q.append(i)

recur(1)
print(sum(visited)-1)