[2606번] 바이러스 / python3 (feat. DFS, BFS 2가지 방법으로)

문제 링크: https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

DFS와 BFS를 잊기 전에 더 풀어보기 위해!!

<단계별로 풀어보기>카테고리로 들어가서 관련문제를 더 풀어보기로 했다.. 😂

 

 

🎈방법 1. DFS 깊이우선 탐색

🎈방법 2. BFS 너비우선 탐색

 

---

🎈방법 1. DFS 깊이 우선탐색

 

---

❌ DFS 1~3차시도 실패

# 1차시도 cnt를 이용해서 알아내기------------------
 
n=int(input())  #컴퓨터의 수
link=int(input())   #연결 쌍의 수
 
graph=[[0]*(n+1) for _ in range(n+1)]   #맵 프레임
visit=[0]*(n+1)     #방문기록 리스트
 
 
#맵 프레임에 자료 입력
for _ in range(link): 
    link1,link2=map(int,input().split())
    graph[link1][link2] = graph[link2][link1]=1     
 
 
def dfs(x):
    visit[x]=1
    for i in range(1,n+1):
        #조건: 방문기록 없고, 연결되어있으면
        if visit[i]==0 and graph[x][i]==1:  
            dfs(i)
            
dfs(1)
cnt=0
for i in range(1,n):
    if visit[i]==1: #방문기록리스트에서 1인것 카운트
        cnt+=1
print(cnt)

---

❓ 정답은 ??

n=int(input())  #컴퓨터의 수
link=int(input())   #연결 쌍의 수
 
graph=[[0]*(n+1) for _ in range(n+1)]   #맵 프레임
visit=[0]*(n+1)     #방문기록 리스트
 
 
#맵 프레임에 자료 입력
for _ in range(link): 
    link1,link2=map(int,input().split())
    graph[link1][link2] = graph[link2][link1]=1
 
result=[] #방문한 정점 숫자 리스트
def dfs(x):
    visit[x]=1
    for i in range(1,n+1):
        #조건: 방문기록 없고, 연결되어있으면
        if visit[i]==0 and graph[x][i]==1: 
           result.append(i)
            dfs(i)
    return len(result)
 
print(dfs(1))

---

💯 풀이 과정

cnt도 방법이 될 수 있겠지만 복잡해지면서 틀리는 것 같아서 len( )방법을 사용하기로 에휴

(cnt로 해보려고 했는데 어디서 잘못되었는지 계속 오답만 나오더라....ㅠㅠ)

 

방문했던 i 정점 숫자들을 리스트에 넣고 그것의 길이로 답을 구했다.

 

 

 

 

 

---

🎈방법 2. BFS 너비 우선탐색

---

❌ BFS 1~3차시도 실패

요것도 3번이나 걸쳐서 시도....ㅠ

que리스트는 방문 검사하면서 하나씩 빼다 보니 쌓이지 않는데, 이걸 검사했으니 안나오는 게 당연하지

# 1~3차시도(실패)-----------------------------------
n=int(input())  #컴퓨터 수
link=int(input())   #연결 수
 
graph=[[0]*(n+1) for _ in range(n+1)] #맵프레임
visit=[0]*(n+1) #방문기록 체크
 
for _ in range(link):   #맵 데이터 만들기
    link1,link2=map(int,input().split())
    graph[link1][link2]=graph[link2][link1]=1
 
from collections import deque
 
def bfs(x):
    que=deque()     #큐형식
    que.append(x)   #방문 검사할 리스트
    visit[x]=1      #방문했으니 1로 체크
    
    while que:
        x=que.popleft()
        for i in range(n+1):
            if visit[i]==0 and graph[x][i]==1:
                que.append(i)   #검사할 숫자리스트 넣기
                visit[i]=1  #검사했으니 1로 체크
    return que
 
print(len(bfs(1)) - 1)  #원인이 되었던 1번 컴퓨터 1대는 빼야함

 

---

❓ 정답은 ??

n=int(input())  #컴퓨터 수
link=int(input())   #연결 수
 
graph=[[0]*(n+1) for _ in range(n+1)] #맵프레임
visit=[0]*(n+1) #방문기록 체크
 
for _ in range(link):   #맵 데이터 만들기
    link1,link2=map(int,input().split())
    graph[link1][link2]=graph[link2][link1]=1
 
from collections import deque
 
def bfs(x):
    result=[x]      #걸린 컴퓨터 알아보기
    que=deque()     #큐형식
    que.append(x)   #방문 검사할 리스트
    visit[x]=1      #방문했으니 1로 체크
    
    while que:
        x=que.popleft()
        for i in range(n+1):
            if visit[i]==0 and graph[x][i]==1:
                result.append(i)    #걸린 컴퓨터리스트 넣기
                que.append(i)   #검사할 숫자리스트 넣기
                visit[i]=1  #검사했으니 1로 체크
    return result
 
# result=[1,2,5,3,6]
print(len(bfs(1)) - 1)  #원인이 되었던 1번 컴퓨터 1대는 빼야함

---

💯 풀이 과정

result리스트를 만들어 걸린 컴퓨터를 알아보기로 했다... 뚜둥..

드디어 나왔다! 제발 헷갈리지 말자..

---

😎오늘의 한줄평: 문제를 보고 DFS가 편할지 BFS가 편할지 판단해보고 사용해보쟈...  (BFS 넘나 머리 아픈것.... 최단거리문제는 어쩔수 없겠지)