백준 | 바이러스 (2606) | 파이썬(Python)

백준 | 바이러스 (2606) | 파이썬(Python)

반응형

| 문제 설명

2606번 문제는 그래프 탐색 기본 문제로, DFS, 혹은 BFS를 이해했다면 풀 수 있다.

고려해야 할 포인트

1. 1번 포인트와 연결되어 있는 컴퓨터 탐색

2. 출력시, 1번 컴퓨터는 제외(1번 컴퓨터로 인해 바이러스 걸린 컴퓨터의 수만 출력)

3. 시작 노드는 1번으로 한다.

| 풀이 과정

문제에서 주어진 입력값 들어갈 변수 설정

N = 컴퓨터 수

M = 직접 연결되어 있는(인접한) 컴퓨터 쌍의 수

graph = 딕셔너리 형태로 key값에는 컴퓨터, value값에는 key값의 컴퓨터와 연결된 컴퓨터들 추가

컴퓨터들의 연결여부 판단하기 위해 visited 리스트 자료형 생성

DFS 함수 정의 (BFS로 해도 상관 없음)

| 최종 코드

from collections import defaultdict # DFS 함수 정의 def dfs(graph, v, visited): # 현재 노드 방문 처리 visited[v] = True # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 1번은 제외되어야 하기 때문에 -1 return visited.count(True) - 1 N = int(input()) M = int(input()) # collections 모듈의 defaultdict 함수를 이용하여 딕셔너리의 value를 리스트로 default graph = defaultdict(list) # Key = 컴퓨터 번호, Value = Key 컴퓨터와 연결된 컴퓨터들 for _ in range(M): a, b = map(int, input().split()) # defaultdict로 value가 리스트로 되어있기 때문에 append()를 통해 원소 추가 graph[a].append(b) graph[b].append(a) # 각 노드가 방문된 정보를 리스트 자료형으로 표현(False: 미방문, True: 방문) visited = [False] * (N+1) print(dfs(graph, 1, visited))

풀이 중 실수했던 기록

현재 나의 고질적인 문제: 주어진 문제를 꼼꼼하게 확인하지 못 한다는 것. 세 번째 줄부터는 '둘째 줄의 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍'이 주어진다고 했지만 나는 컴퓨터별로 연결되어 있는 컴퓨터 번호를 주어지는 것으로 착각했다. 앞으로 문제를 풀 때, 더 집중해서 주어진 조건들을 제대로 파악할 수 있도록 해야겠다. 처음에 visited 리스트 자료형을 만들 때, 인덱스를 고려하지 못하고 [False] * N 으로 했었다.

다행히 Index Error를 보고 문제의 원인을 빨리 찾을 수 있었다.

| 공부한 내용 정리

1. BFS

BFS(너비우선탐색): 탐색할 때 너비를 우선으로 하여 탐색 수행

BFS를 하면서 각 노드에 대해서 최단 경로의 길이를 구할 수 있다.

큐(Queue)를 이용하여 탐색

시간 복잡도:

인접리스트로 구현시: O(2N)

인접행렬로 구현시: O(N^2)

2. DFS

DFS(깊이우선탐색): 탐색할 때 깊은 것을 우선으로 탐색

주로 스택(Stack) 사용

시간 복잡도: O(2N)

* 레퍼런스

https://m.blog.naver.com/ndb796/221230944971

https://m.blog.naver.com/ndb796/221230945092

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/dashboard

※ 부족한 점이 많기 때문에 수정 및 보완해야 할 부분이 있다면 댓글로 가르쳐주시면 감사하겠습니다:)

반응형

from http://dapsu-startup.tistory.com/47 by ccl(A) rewrite - 2021-08-20 03:01:46