<DFS BFS> 백준 2606번. 바이러스 + 다시

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

2606번: 바이러스

import sys
input = sys.stdin.readline

cnt = 0

##함수
def dfs_virus(start):
  global cnt
  visited[start] = 1
  print(start,"에서 실행")
  
  for i in graph[start]:
    if visited[i] == 0: #방문 안했으면
      dfs_virus(i)
      cnt += 1

#####main#########################
n = int(input()) ## 컴퓨터 개수
link = int(input())
visited = [0]*(n+1)
graph = [ []*(n+1) for _ in range(n+1) ] 
# [ [], [], [] ...   ] 이런 식으로 생성


for i in range(link):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)  ##위 과정을 통해 모두 추가됨



print("---------\n인접노드리스트 graph", *graph,sep="\n", end = "\n------\n")
dfs_virus(1)  
print(cnt)

결과는 다음과 같다.

우선 <주의할 점>

1. graph = [   []*(n+1) for _ in range(n+1)   ]

위 코드를 실행하면 [  [], [], []..   ]가 생성됨.

n+1만큼 해주는 이유는 0번노드는 없기 때문에 1번부터 작성하기 위해 하나 추가

 

2. graph[a].append(b)와 graph[b].append()

대애박.. a번째 그래프에 b를 추가하고 b번째 그래프에 a를 추가한다...

그럼 저 옆에 출력된 것처럼 인접노드리스트가 생성된다...

 

 

 

 

---

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
graph = [ []*(n+1) for _ in range(n+1) ]
visited = [False] * (n+1)

for _ in range(m):
  a, b = map(int , input().split())
  graph[a].append(b)
  graph[b].append(a)
print(*graph, sep = "\n")

def bfs(start):
  visited[start] = True
  q = deque()
  q.append(start)
  while q:
    now = q.popleft()
    for i in graph[now]:
      if visited[i] == False :
        visited[i] = True
        q.append(i)


def dfs(start):
  visited[start] = True
  for i in graph[start]:
    if visited[i] == False:
      visited[i] = True
      dfs(i)
      
dfs(1)       
print(visited.count(True)-1) # 본인 노드 제와\ㅣ

3일만에 다시 풀어봤다 으히히 dfs랑 bfs 다 구해봐따