개발 공부/Algorithm
[ 백준 ] 2606번 : 바이러스 (파이썬)
뺙사우르수
2020. 6. 20. 12:02
728x90
문제 )
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어��
www.acmicpc.net
[ 풀이 ]
그래프 탐색에 대한 문제이다. 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()
728x90