파이썬 백준 2606번 : 바이러스 -DFS, BFS

문제

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

2606번: 바이러스

 

 

풀이

결국 그래프가 주어졌을 때 1번 노드의 연결요소의 개수를 세는 문제이다. 

 

sol1 ) BFS와 인접 리스트 이용

import sys
from collections import deque

def BFS(Graph, start, visited):
    queue=deque([start])
    visited[start]=True #노드 방문 처리
    result=0
    while queue: #queue가 비어있지 않은 경우 반복
        result+=1 # 연결요소의 개수 세기
        V=queue.popleft() # queue의 첫번째 노드(V) 방문
        for i in Graph[V]: # V노드의 연결요소 중
            if not visited[i]: # 방문하지 않은 노드를
                queue.append(i) # queue에 넣음
                visited[i]=True # queue에 넣은 노드 방문처리
    return result # 연결요소의 개수 반환

if __name__ == "__main__":
    node=int(sys.stdin.readline())
    line=int(sys.stdin.readline())
    Graph=[]
    for _ in range(node+1):
        Graph.append([])

    for _ in range(line): #Graph 만들기
        node1, node2 = map(int, sys.stdin.readline().split(' '))
        Graph[node1].append(node2)
        Graph[node2].append(node1)

    visited = [False] * (node + 1) 
    result=0
    print(BFS(Graph,1,visited)-1) #BFS의 값에서 1노드를 제외하고 출력

 

sol2 ) DFS와 인접행렬이용

import sys

def DFS():
    while(stack):
        current=stack.pop()
        global cnt
        if current not in visited:
            visited.append(current)
            cnt+=1
        for j in range(N+1):
            if adj_matrix[current][j] and j not in visited:
                stack.append(j)

N=int(sys.stdin.readline())
M=int(sys.stdin.readline())
cnt=0
adj_matrix=[[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    start,end=map(int,sys.stdin.readline().split())
    adj_matrix[start][end]=1
    adj_matrix[end][start]=1

stack=[1]
visited=[]
DFS()
print(cnt-1)