BOJ 2606. 바이러스 (Python)
2021. 2. 22. 23:18ㆍProblem Solving/BOJ
BOJ 2606. 바이러스
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
풀이
DFS를 통해 탐색한 노드의 수 - 1
(1번 컴퓨터는 제외) 를 구해주면 된다.
틀렸습니다 를 굉장히 많이 봤는데 이유는 그래프를 단방향으로 만들어 주어서 이다. 테스트 케이스에선 잘 나와서 생각하지 못했다.
앞으로 방향
을 언급하지 않으면 양방향으로 해 주어야 하는것을 잊으면 안되겠다.
재귀로도 풀 수 있다.
소스코드
import sys from collections import defaultdict N = int(input()) # 노드(컴퓨터) 수 M = int(input()) # 간선(컴퓨터 쌍)의 수 computer = defaultdict(list) for _ in range(M): a, b = map(int, sys.stdin.readline().split()) computer[a].append(b) computer[b].append(a) discoverd = [] stack = [1] # DFS while stack: v = stack.pop() if v not in discoverd: discoverd.append(v) for w in computer[v]: stack.append(w) print(len(discoverd) - 1)

반응형
'Problem Solving > BOJ' 카테고리의 다른 글
BOJ 11279. 최대 힙 (Python) (0) | 2021.02.23 |
---|---|
BOJ 1927. 최소 힙 (Python) (0) | 2021.02.23 |
BOJ 1003. 피보나치 함수 (Python) (0) | 2021.02.19 |
BOJ 1764. 듣보잡 (Python) (0) | 2021.02.19 |
BOJ 1620. 나는야 포켓몬 마스터 이다솜 (Python) (0) | 2021.02.19 |