[백준] 2606번 바이러스 - (Python)

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

전형적인 DFS, BFS로 구현하는 문제입니다. 여기서 요구하는 것은 1번 노드에서 연결된(문제에서는 감염시키는) 노드의 총 개수를 구하는 문제와 동일합니다.

 

단, 1번 노드 자신은 제외하고 출력해야 하므로 최종 출력 시 주의 해야합니다.

 

※ 고려사항

1. 입출력처리 및 노드와 간선 배열처리

2. DFS 또는 BFS 구현

3. 최종 출력시 1번 노드 제외

 

---

1. 입출력처리 및 노드와 간선 배열처리

먼저 방문처리를 할 배열과 간선과 노드를 저장할 배열 2개를 생성 해줍니다.

간선과 노드를 저장하는 배열의 경우, 2차원 배열을 통해 해당 리스트에는 각 인덱스마다 연결되고 있는 노드를 삽입합니다.

노드 번호와 배열의 index 순서를 동일하게 하기 위해, 노드의 크기 + 1 만큼의 배열크기를 할당합니다.

import sys
from collections import deque

# node, 간선, 시작위치
n = int(sys.stdin.readline())
node = int(sys.stdin.readline())

# 방문 리스트
visited = [0] * (n+1)
graph = [[] for _ in range(n+1)]

# 인접 노드 구현
for i in range(node):
    a, b = map(int, sys.stdin.readline().split())

    # 연결 노드는 각 배열에 할당 ex) [[], [2], [1], []]
    graph[a].append(b)
    graph[b].append(a)

 

graph를 출력해보면 다음과 같이 출력됩니다.

[[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]

 

2. DFS 또는 BFS 구현

 

그래프 문제는 DFS 또는 BFS로 구현할 수 있습니다.

DFS는 재귀와 Stack을 이용한 풀이, BFS는 Queue를 이용하여 문제를 해결할 수 있습니다.

DFS는 깊이 우선 탐색으로 노드의 깊이순서로 탐색하게 되고, BFS는  너비 우선 탐색으로 노드를 방문합니다.

DFS, BFS 그림설명

 

DFS, BFS를 가지고 모두 구현해 보았습니다. 그래프 문제를 구현할 때는 다양한 접근법이 중요함으로 2가지 방법 모두를 연습하는게 좋다고 생각됩니다.

 

DFS 재귀

# dfs 재귀 구현
def dfs(v):

    # 방문처리
    visited[v] = 1

    # 방문처리 되지 않았으면 재귀
    for i in graph[v]:
        if visited[i] == 0:
            dfs(i)

 

DFS Stack

# dfs stack 구현
def dfs_stack(v):

    # 스택생성
    stack = [v]

    # 스택 empty 때까지
    while stack:

        s = stack.pop()

        # 방문되지 않았으면 방문처리
        if visited[s] == 0:
            visited[s] = 1

            # 해당 노드 연결요소 stack에 삽입
            for w in graph[s]:
                stack.append(w)

 

BFS

# bfs 구현
def bfs(v):
    
    # 방문처리
    visited[v] = 1

    # 큐 생성
    queue = deque([v])

    # 큐가 empty때 까지
    while queue:

        # 먼저 삽입된 노드 pop
        q = queue.popleft()

        # q와 연결된 모든 요소 확인
        for i in graph[q]:
            
            # 방문되지 않은 노드는 queue에 삽입 후, 방문처리
            if visited[i] == 0:
                queue.append(i)
                visited[i] = 1

 

3. 최종 출력시 1번 노드 제외

방문리스트는 초기값이 모두 0으로 초기화 되어있습니다. 따라서 시작노드인 1번 노드를 제외하고 출력해야 합니다.

# 1에서 시작임으로 1제외하고 출력
print(visited.count(1)-1)

---

전체코드

import sys
from collections import deque

# node, 간선, 시작위치
n = int(sys.stdin.readline())
node = int(sys.stdin.readline())

# 방문 리스트
visited = [0] * (n+1)
graph = [[] for _ in range(n+1)]

# 인접 노드 구현
for i in range(node):
    a, b = map(int, sys.stdin.readline().split())

    # 연결 노드는 각 배열에 할당 ex) [[], [2], [1], []]
    graph[a].append(b)
    graph[b].append(a)

print(graph)

# dfs 재귀 구현
def dfs(v):

    # 방문처리
    visited[v] = 1

    # 방문처리 되지 않았으면 재귀
    for i in graph[v]:
        if visited[i] == 0:
            dfs(i)

# dfs stack 구현
def dfs_stack(v):

    # 스택생성
    stack = [v]

    # 스택 empty 때까지
    while stack:

        s = stack.pop()

        # 방문되지 않았으면 방문처리
        if visited[s] == 0:
            visited[s] = 1

            # 해당 노드 연결요소 stack에 삽입
            for w in graph[s]:
                stack.append(w)

# bfs 구현
def bfs(v):
    
    # 방문처리
    visited[v] = 1

    # 큐 생성
    queue = deque([v])

    # 큐가 empty때 까지
    while queue:

        # 먼저 삽입된 노드 pop
        q = queue.popleft()

        # q와 연결된 모든 요소 확인
        for i in graph[q]:
            
            # 방문되지 않은 노드는 queue에 삽입 후, 방문처리
            if visited[i] == 0:
                queue.append(i)
                visited[i] = 1
                
dfs(1)
dfs_stack(1)
bfs(1)

# 1에서 시작임으로 1제외하고 출력
print(visited.count(1)-1)

---

항상 그래프 알고리즘을 구현할 때, 한 가지 방법으로만 생각하게 됩니다. 또는 생각은 했으나, 구현을 2가지 다 하지 않았습니다. 그러나, DFS, BFS 모두 핵심적인 알고리즘이기 때문에 한 가지 방법만 고수하지 말고 문제에 접근할 때, 모든 방식으로 구현해보는 습관을 지녀보는 것이 좋을 듯 합니다.

설명의 오류나, 궁금하신 점은 언제든 피드백 해주시면 감사하겠습니다 ^~^