[백준_Python] 2606 - 바이러스 [실버 3]

황준성·2024년 11월 13일

BOJ_Python

목록 보기

12/70

문제

예제 입력 1

예제 출력 1

문제 이해

프로그래머스 네트워크 문제와 비슷하지만 그것보단 좀 쉬운 문제이다.

1번 컴퓨터와 연결되어 있는 컴퓨터를 모두 탐색한 다음, 그 컴퓨터 수를 출력하는 방식이다. 1번 컴퓨터와 연결되어 있는 것만 찾으면 되기 때문에 프로그래머스의 "네트워크"보다는 훨씬 간단하다.

아직 DFS/BFS를 배우는 과정이라서 이해도가 많이 낮다. 사실 이해가 잘 안되서 DFS에 대해서 서칭하던 중에 "개발자로 취직하기"라는 사람의 DFS 강의를 알게되었다. 맛보기 강의의 문제풀이 영상이 이 "바이러스"였고, 강의가 너무 좋다. 이 강의를 완강하면 아마 DFS 문제는 어느정도 풀 수 있을 것 같다는 생각이 든다. 그래서 이 문제를 시작으로 강의를 구매해서 보려고 한다

https://www.inflearn.com/course/python-%EB%AC%B8%EA%B3%BC%EC%83%9D-%EC%9D%B4%ED%95%B4%ED%95%98%EB%8A%94-dfs-%EC%9E%85%EB%AC%B8?inst=74b0f047

혹시 이 글을 보는 나같이 DFS/BFS 감이 안잡히는 코린이가 있다면 이 강의의 무료 강의를 한번 보는 것을 추천한다.

DFS코드

# 백준 2606번 바이러스 DFS

def DFS(idx):
    global graph, visited, answer
    visited[idx] = True
    answer += 1

    for i in range(N + 1):
        if not visited[i] and graph[idx][i]:
            DFS(i)

# 0. 입력 및 초기화
N = int(input())
M = int(input())

graph = [[False] * (N + 1) for _ in range(N + 1)]
visited = [False] * (N + 1)
answer = 0

# 1. graph 연결 값 넣기
for _ in range(M):
    x, y = map(int, input().split())
    graph[x][y] = True
    graph[y][x] = True


# 2. DFS 호출
DFS(1)

# 3. 출력
print(answer - 1)

DFS 그래프로 이해하기

"개발자로 취직하기"님의 방식을 이용했지만, 스스로 표를 만들면서 이해하려 했다. 다음은 내가 만든 표이다.

예제 입력1을 기준으로 만들었다.

왼쪽은 컴퓨터간의 연결을 표로 만든 것이고, 오른쪽은 그 연결을 이차원 배열로 나타낸 것이다. 2차원 배열로 나타내는 게 DFS의 흐름을 이해하기 편해서 그렇게 표현을 했다.

이건 개발자로 취직하기님의 방식을 토대로 만들었다. 이렇게 자꾸 만들면서 DFS문제를 풀다보면 DFS 감을 찾을 수 있을거라고 한다. 확실히 머리로만 이해하는 것보다는 이천만배는 나을 것 같다. 표를 보는 법을 알면 보기보다 이해하기 수월하다.

BFS 코드

# 백준 2606번 BFS

import sys
input = sys.stdin.readline

from collections import deque

def BFS(idx):
    global visited, count
    queue = deque()

    # BFS는 처음 값은 직접 넣어줘야 함
    queue.append(idx)
    visited[idx] = True

    while queue:

        number = queue.popleft()

        for value in graph[number]:
            if not visited[value]:
                # BFS는 큐에 값을 넣으면서 방문 처리
                queue.append(value)
                visited[value] = True
                count += 1



# 0. 입력 및 초기화
node_num = int(input())
edge_num = int(input())
# 컴퓨터 번호가 1번부터
graph = [[] for _ in range(node_num + 1)]
visited = [False] * (node_num + 1)
count = 0

# 1. 연결 정보 입력
for i in range(edge_num):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

# 2. 오름차순 정리
for i in range(1, node_num + 1):
    graph[i].sort()

# 3. BFS호출
BFS(1)

# 4. 출력
print(count)

DFS 한 놈만 패고 난후, 이제는 BFS를 공략하고 있다. DFS와 BFS 문제는 따로 나뉘어져 있는 게 아니어서 DFS로 풀었던 문제를 BFS로 풀어보고 있다.

틀린 코드

def BFS(idx):
    global visited, count
    queue = deque()

    # BFS는 처음 값은 직접 넣어줘야 함
    queue.append(idx)
    visited[idx] = True

    while queue:

        number = queue.popleft()
        count += 1

        for value in graph[number]:
            if not visited[value]:
                # BFS는 큐에 값을 넣으면서 방문 처리
                queue.append(value)
                visited[value] = True