[Python] 백준 온라인 저지 2606

목차

문제

---

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

2606번: 바이러스

 

설계&풀이

---

가장 기초적인 DFS/BFS 문제다.

이전에 비슷한 문제를 풀어서인지, 동일한 폼으로 풀 수 있었다.
풀면서 새로 안 사실이 있는데, 파이썬에선 전역변수 설정을 별도로 해줘야 하는 것이었다.

dfs와 bfs 함수 안에 cnt로만 해두면 알아서 전역변수로 찾아가는건줄 알았는데, 그게 아니라 global로 선언해줘야 되더라; 몰랐음..

기초적인 문제다보니 특별한 설명은 필요없을듯 하다..
아, 그리고 dfs를 자꾸 재귀로 푸는 습관이 있는데.. 이렇게 하지말고 스택으로 푸는 습관을 들이는 것이 좋을 것 같다

풀이는 간단하게 다음과 같다.

먼저 기본적인 정보들을 세팅해주고..

n = int(input())
m = int(input())
cnt = 0

visited = [0] * (n + 1)
graph = [ [] for _ in range(n + 1)]

 간선 정보를 받을 for문을 돌려준다.

# 간선정보 매핑
for _ in range(1, m + 1):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

dfs와 bfs 함수는 다음과 같이 설정했고. 나중에 호출해주면 끝임.

def dfs(v):
	# v번째 노드 방문처리
    visited[v] = 1
    global cnt
    # graph의 v번째 노드 안에서 for문 돌기
    for i in graph[v]:
    	# 만약 방문하지 않은곳이라면, 재귀 호출해주고 cnt += 1 해주기
        if visited[i] == 0:
            dfs(i)
            cnt += 1

def bfs(v):
	# v번째 노드 방문처리
    visited[v] = 1
    # [v] 만큼의 deque 생성
    q = deque([v])
    # 큐의 크기만큼 돌기
    while q:
    	# 큐에서 뽑아낸 x라는 친구
        x = q.popleft()
        # 그래프의 x번째 노드 인자 수만큼 for문 돌기, 이하 생략
        for i in graph[x]:
            if visited[i] == 0:
                visited[i] = 1
                global cnt
                cnt += 1
                q.append(i)

 

코드 GIT 주소

---

https://github.com/kkkapuq/AlgorithmStudy/blob/main/Python/220517_BOJ_2606_%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A4/HyungJoonCho.py

GitHub - kkkapuq/AlgorithmStudy: 알고리즘 문제풀이

 

코드

---

import sys
from collections import deque
sys.setrecursionlimit(10000)

def dfs(v):
    visited[v] = 1
    global cnt
    for i in graph[v]:
        if visited[i] == 0:
            dfs(i)
            cnt += 1

def bfs(v):
    visited[v] = 1
    q = deque([v])
    
    while q:
        x = q.popleft()
        for i in graph[x]:
            if visited[i] == 0:
                visited[i] = 1
                global cnt
                cnt += 1
                q.append(i)

n = int(input())
m = int(input())
cnt = 0

visited = [0] * (n + 1)
graph = [ [] for _ in range(n + 1)]

# 간선정보 매핑
for _ in range(1, m + 1):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

bfs(1)
print(cnt)

 

결과

---

 

 

구독 및 하트는 정보 포스팅 제작에 큰 힘이됩니다♡