백준 - 2606번(DFS,BFS)

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

2606번: 바이러스

 

import sys
from collections import deque

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

arr = deque([deque([]) for _ in range(n+1)]) #2차원 덱 만들기

for _ in range(m):
    tmp = []
    tmp = list(map(int,sys.stdin.readline().split()))
    arr[tmp[0]].append(tmp[1]) #양방향 간선 추가
    arr[tmp[1]].append(tmp[0]) #양방향 간선 추가

visited = [0 for _ in range(n+1)] #방문 체크 리스트

def BFS():
    while arr[1]:
        t = arr[1].popleft()
        if len(arr[t]) > 0 and t != 1: #1번 리스트는 bfs로 탐색x
            while arr[t]: #1번 컴퓨터를 통해서 갈 수 있는 컴퓨터 전부 추가
                x = arr[t].popleft()
                arr[1].append(x)

        if visited[t] == 0:
            visited[t] = 1 #방문 처리

BFS()
ans = 0
for i in visited:
    if i == 1:
        ans = ans + 1

print(ans - 1) #1번은 빼기 때문에 마지막에 -1

1. BFS를 이용한 풀이)

문제에서 시작은 무조건 1번 컴퓨터에서 한다.

1번 컴퓨터부터 시작해서 BFS 탐색을 하면 1번 컴퓨터에 연결되어 있는 컴퓨터를 전부 방문 처리할 수 있다.

그럼 방문처리 된 애들은 바이러스에 감염된 애들이다.

 

import sys
from collections import deque

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

arr = [[] for _ in range(n+1)]

for _ in range(m):
    tmp = []
    tmp = list(map(int,sys.stdin.readline().split()))
    arr[tmp[0]].append(tmp[1]) #양방향 간선 추가
    arr[tmp[1]].append(tmp[0]) #양방향 간선 추가

visited = [0 for _ in range(n+1)]
def DFS(arr,visited,s):
    visited[s] = 1 #방문처리
    while arr[s]:
        t = arr[s].pop() #시작지점설정
        if visited[t] == 0:
            DFS(arr,visited,t) #시작지점 변경후 재귀 호출

DFS(arr,visited,1)

ans = 0
for i in visited:
    if i == 1:
        ans = ans + 1

print(ans - 1) #1번 컴퓨터는 빼기 때문에 마지막에 -1

2. DFS를 이용한 풀이)

DFS풀이에서는 시작 지점이 중요하다.

시작 지점에 존재하는 간선들을 시작 지점으로 해서 DFS로 재귀 호출해주고 호출 후 방문 처리를 해준다. 

그럼 방문처리 된 애들은 바이러스에 감염된 애들이다.