그림의 출처는 아래 블로그 글입니다. 많은 도움을 받았습니다.

[백준] 2606 바이러스 - Python (그래프 탐색)

여러 번 다양한 좋은 글들을 글을 읽고도 구현을 못하다가 이제 쉬운 문제를 겨우 구현했습니다.

어깨 너머로 구현하시는 것을 많이 보고 이야기를 주워 듣다 보니-

그래프와 트리 문제 구현 연습을 많이 해 보려구요.

위 페이지에 있었던 깊이우선과 너비우선 모두로 구현했습니다.

이래 블로그 글을 읽고 혼자 코드를 구현해 보고 비교하면서 수정했어요.

먼저 DFS입니다.

import sys

def dfs(v):
    visited[v]=1
    for nx in graph[v]:
        if visited[nx]==0:
            dfs(nx)

raw=list(map(str.rstrip,sys.stdin.readlines()))
n = int(raw[0]) #computers
v = int(raw[1]) #connections
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)
for line in raw[2:]:
    a,b = map(int,line.split())
    graph[a].append(b)
    graph[b].append(a)

dfs(1)
print(sum(visited)-1)

그리고 BFS입니다. 2차원 토마토 때보다 구현이 어렵게 느껴졌어요.

import sys
from collections import deque

def bfs(v):
    visited[v]=1
    queue = deque([1])
    while queue:
        curr=queue.popleft()
        for nx in graph[curr]:
            if visited[nx]==0:
                queue.append(nx)
                visited[nx]=1

raw=list(map(str.rstrip,sys.stdin.readlines()))
n = int(raw[0]) #computers
v = int(raw[1]) #connections
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)
for line in raw[2:]:
    a,b = map(int,line.split())
    graph[a].append(b)
    graph[b].append(a)

bfs(1)
print(sum(visited)-1)

비슷한 문제라고 느껴서 이런 문제도 풀었어요.

defaultdict(bool) 이라는 유용한 도구도 알게 되었어요!

from sys import stdin
from collections import defaultdict

raw = [tuple(x.split()) for x in list(map(str.rstrip, stdin.readlines()[1:]))]

dance = defaultdict(bool)
dance['ChongChong'] = True
answer = 1 

while raw: #총총이 등장 전까지는 날려줍니다.
    a,b = raw[0]
    if a=='ChongChong' or b=='ChongChong':
        break
    else:
        raw.pop(0)
 
for a,b in raw:#등장 후 데이터 기반으로 탐색합니다.
    if dance[a]:
        if not dance[b]:
            dance[b] = True 
            answer += 1 
    elif dance[b]:
        dance[a] = True 
        answer += 1 
print(answer)

그런데 이 문제는 트리라고 합니다.

그래서 그래프와 트리의 차이점을 알아봤습니다.(들었는데 잘 기억이 안 나서….)