백준 2606번 파이썬 _ 바이러스

입력을 받아 2차원배열로 연결된 노드를 표현하는 그래프를 만들고, dfs혹은 bfs를 통해 노드를 방문

 

최종적으로 1번(감염된노드)로부터 연결되어있어서 방문된 노드의 개수를 출력

 

내코드 :

dfs로 해도 되는데 bfs로 풀어봄 ( 큐 이용 )

from collections import deque

p = int(input())
q = int(input())

graph = [[] for _ in range(p+1)]

for _ in range(q):
  n, k = map(int, input().split())
  graph[n].append(k)
  graph[k].append(n)

visited = [False] * (p+1)

def bfs(graph, start, visited):
  queue = deque([start])

  visited[start] = True

  while queue:
    v = queue.popleft()
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True
  
  print(visited.count(True)-1)
    
bfs(graph, 1, visited)

이차원배열 만드는 방법을 자꾸 까먹는다...

 

포문으로 안하고 연산자(*) 로 만들면 복제되는거라서 하나바꾸면 전체배열이 다바뀜

항상 포문으로 하는 습관!! [ [0] * n for _ in range(m)]

 

 

다른분 코드

다른분 코드

dfs로 구현할때 굳이 visited 배열을 미리 만들어서 false로 초기화해놓지 않고 방문될때 그냥 리스트에 추가하는방식으로도 풀수 있다

 

그러면 함수 인자로 visited리스트 안줘도댐