[알고리즘] BOJ 2606번 - 바이러스(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

3 / 50

 

탐색

3 / 50(NEW!)

 

기초 동적 프로그래밍

3 / 50

 

투포인터

0 / 10

---

문제

2606번: 바이러스 (acmicpc.net)

2606번: 바이러스

→ solved.ac 기준 실버 3

---

문제 해결 아이디어

그림만 보고 그래프 탐색임을 일단 유추,

시작 노드가 1번이고, 연결된 노드의 수를 출력

dfs로 1번 노드부터 방문하기

마지막에 방문 정보로 출력

---

구현

내 풀이

def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
	visited[v] = True
	# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, i, visited)
      
n = int(input())
m = int(input())

graph = [-1] * n
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if (graph[a] == -1):
    graph[a] = [b]
  else:
    graph[a].append(b)
  if (graph[b] == -1) :
    graph[b] = [a]
  else:
    graph[b].append(a)
    
if (m == 0):
  print(0)
else:
  visited = [False] * n
  dfs(graph, 0, visited)
  print(visited.count(True) - 1)

---

메모

• 걸린 시간: 20분

---

마치며

난이도 조정이 제일 어렵다..ㅋㅋㅋㅋㅋ

일단 solved.ac 보고 차례로 보고 있는데

등급 자체는 1 ~ 2 차이 나는데

왜 실제 체감 난이도는 하늘과 땅차이일까