[ 백준 ] 2606번 : 바이러스 (파이썬)

문제 )

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

2606번: 바이러스

 

[ 풀이 ]

그래프 탐색에 대한 문제이다. BFS, DFS 방법으로 둘 다 구현해 보았다. 

먼저, DFS방법으로 푼 코드이다. 재귀함수를 이용해준다. 

 

- Python code (DFS )

visit=[1]
def DFSWorm(current):
    global count, visit
    for i in range(1,n+1):
        # 바이러스에 걸리지 X & 길이 연결되어있는 경우
        if i not in visit and way[current][i]==1: 
            count+=1
            visit.append(i)
            DFSWorm(i)

n=int(input())
line=int(input())
# 경로를 행렬로 만들어 줘야함 N*N 행렬 - 인접행렬 통해 접근 
way=[[0]*(n+1)for i in range(n+1)]
count=0
for i in range(line):
    x,y=map(int,input().split())
    way[x][y]=1
    way[y][x]=1

DFSWorm(1)
print(count)

 

 

BFS로 푼 코드이다. Queue를 이용하여 구현해주었다. 

- Python code (BFS )

def BFSWorm():
    bcount=0
    visited=[1]
    queue=[1]
    while queue:
        v=queue.pop(0)
        # 바이러스에 걸리지 X & 길이 연결되어있는 경우
        for i in range(1,n+1):
            if i not in visited and way[v][i]==1:
                bcount+=1
                visited.append(i)
                queue.append(i)
    print(bcount)


n=int(input())
line=int(input())
# 경로를 행렬로 만들어 줘야함 N*N 행렬 - 인접행렬 통해 접근 
way=[[0]*(n+1)for i in range(n+1)]
for i in range(line):
    x,y=map(int,input().split())
    way[x][y]=1
    way[y][x]=1

BFSWorm()