[python] 백준 2606 -바이러스 / bfs / 입력을 다른 풀이들과 다르게 풀었을때

처음 코드에서

https://www.acmicpc.net/board/view/421

글 읽기 - 2606번 '바이러스'문제, 왜 틀리다고 나오는지 잘 모르겠습니다.

와 유사한 오류를 발견해서 다시 한번 갈아 엎고 만들었다. 처음부터 한번에 성공하는건참 어려운일이다;

 

 

(내코드)

from collections import deque

com_num , link= int(input()) , int(input())
virus=[[*map(int , input().split())] for _ in range(link)]

visited = [False]*com_num

queue = deque()
queue.append(1)

count = -1
while queue:
    x=queue.popleft()
    
    if visited[x-1]==True:
        continue
    visited[x-1] = True
    count+=1
    for i,j in virus:
        if i==x :
            queue.append(j)
        elif j==x:
            queue.append(i)

print(count)

 

딱히 리뷰할게 없다. 다른사람보다 너무 코드가 긴거같다;

 

 

https://jiwon-coding.tistory.com/93

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

여기 블로그에 있는 코드가 내가 쓴 코드보다 훨씬 좋아보인다. 

dfs 를 사용해서 문제를 해결했다. 저번에도 그렇고 dfs 는 재귀로 구성하는게 좋다고 했는데 이쪽 블로그에서도 마찬가지로 재귀를 사용해서 풀었다. 

 

n = int(input())
m = int(input())
graph = [[]*n for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
cnt = 0
visited = [0]*(n+1)
def dfs(start):
    global cnt
    visited[start] = 1
    for i in graph[start]:
        if visited[i]==0:
            dfs(i)
            cnt +=1
 
dfs(1)
print(cnt)

 

내가 처음에 고민했던 부분이 입력을 받은 형식에서부터 고민이 되었다. 

내 코드에서 입력을 받는다면 

[[1,2],[2,3],[3,6] .....etc  ] 이렇게 받게 된다. 

이렇게 받게되면 좀 짜증나는게 하나의 리스트에서 앞과뒤 ( 0번째와 1번째) 이걸 다시 재조정하는 과정이 필요하다 ( while 문 자체에서 돌릴때) 근데 이 블로그에서는 애초에 입력받을때  예를들어서 1과 관련되어 있는 노드들이 2,3 이라고한다면 

[1,2,3] , [2,1, etc ..] 이렇게 받게된다. 

이렇게 받는다면 맨처음 index 에 연결되어 있는 노드를 모두 표현할 수 있다. 

그렇게 표현한 후에 dfs 를 사용한다. (재귀를 사용해서 dfs 구하는 걸 다시한번 참고하자) 

 

+) 왜 저렇게 만들어 놓으면 dfs /bfs 할때 편리한지   아래 블로그를 참고하면 예시문제들을 풀때 저런식으로 자료가 나와있다. (익숙해서 좋은건지 아니면 성능자체가 우수한지는 잘 모르겠다)

https://cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

(bfs)

https://chancoding.tistory.com/60

[파이썬] 백준 2606번 바이러스 - BFS방식과 DFS 방식 비교

또 다른 블로그를 보니 더 빠른 시간에 풀수 있다. dfs 에서 큰 차이는 없는 듯 하나 

dic 사용해서 문제를 해결했다. 리스트보다 dic 이  해쉬를 사용하면 더 빠르다 ( 예전에 정리 한 적 있다.).

이런 디테일한 부분에서도 시간을 줄일 수 있구나. 

 

 

bfs 방식도 살펴보자 

from sys import stdin
read = stdin.readline
dic={}
for i in range(int(read())):
    dic[i+1] = set()
for j in range(int(read())):
    a, b = map(int,read().split())
    dic[a].add(b)
    dic[b].add(a)

def bfs(start, dic):
    queue = [start]
    while queue:
        for i in dic[queue.pop()]:
            if i not in visited:
                visited.append(i)
                queue.append(i)
visited = []
bfs(1, dic)
print(len(visited)-1)

음 마찬가지로 '입력' 받을때 차이점이 도두라졌다. 나머지는 고만고만한것 같았고.

근데 여기서 입력을 나처럼받고 나보다더 효율적으로 푼 풀이가 없을까? 찾아보았다만....

 

다들 풀이다 거의 일치한다.

혹시나 입력을 나처럼 받고 고민한 사람들이 있다면 내코드를 보면서 다시생각해보거나 의견을 공유해주면 좋겠다.