[Algorithm/Python][백준] 2606번 바이러스

[BOJ] 2606번 바이러스

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

- 문제 접근

• DFS와 BFS 두가지 방법 모두로 풀어보았다
• 두 방법 모두 가능하지만 이 문제처럼 일반적으로 모든 경우를 다 탐색해야 하는 경우는 DFS, 많은 경우의 수가 있어 (ex 미로) 다 탐색하지 않는 경우 BFS가 선호된다고 한다.
• 찾아보니까 2차원 배열이 아닌 dic을 이용하여 풀기도 하는 것 같다.

- 내 코드

from collections import deque

def bfs(graph):
    queue = deque([1])
    visited[1]==True
    while deque:
        v=queue.popleft()
        for i in range(len(graph[v])):
            if visited[i]==False and graph[v][i]==1:
                queue.append(i)
                visited[i]=True
        if len(queue)==0:
            break
        
        
def dfs(graph, V, visited):
    visited[V]=True
    for i in range(len(graph[V])):
        if visited[i]==False and graph[V][i]==1:
            dfs(graph, i, visited)
    
N=int(input())
M=int(input())

graph = [[0 for col in range(N+1)] for row in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a][b]=1
    graph[b][a]=1
    
visited = [False] * (N+1)
visited[0] = True
    
# bfs(graph)
dfs(graph,1,visited)
print(sum(visited)-2)

- 조금 더 괜찮아 보이는 코드

n = int(input())		# 컴퓨터의 수
m = int(input())		# 연결된 컴퓨터 쌍의 수

# 인접리스트 graph 선언 및 입력받기
graph = [[] for _ in range(n+1)]
for _ in range(m):							# 연결된 컴퓨터 쌍의 수만큼 반복
    x, y = map(int, input().split())		
    graph[x].append(y)
    graph[y].append(x)

visited = [0] * (n+1)	# 방문처리 : 방문한 컴퓨터 수를 출력해야하므로 visited 에 True/False가 아닌 0/1로 처리

def dfs(graph, v, visited):
    visited[v] = 1
    for i in graph[v]:
        if visited[i] == 0:
            dfs(graph, i, visited)
    return True

dfs(graph, 1, visited)
print(sum(visited)-1)	# 방문한 컴퓨터 개수 - 1번 컴퓨터