[Python/BOJ] 백준 2606 바이러스 (dfs)

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

2606번: 바이러스

 

그래프 문제의 기본!! 

굉장히 쉬운 문제로 알고있었는데

파이썬으로  풀려고하니까 생소했다.

 

 

내가 스트레스를 받는걸보니 성장하고 있나보다! 하하 

할수있다!! 아자!

 

 

 

 

 

 

📄 문제

 

이렇게 그래프가 있을때 1부터 바이러스가 전파될때 전염되는 컴퓨터의 개수는??!!

 

 

 

🖌 어떤 생각?

일단 파이썬으로 그래프 문제를 처음 풀어보았기에

이차원 리스트를 만드는 것조차 몰랐다. 

바로 코드찾아보았다.

코드 다 외워버려야지라는 생각을 했다. 

 

<코드 참조>

https://jiwon-coding.tistory.com/93

[백준] 2606번 바이러스 / 파이썬(python)

 

 

지금 어떻게 이 문제를 푸는게 중요한게 아니라

파이썬의 문법을 이 문제를 통해 배워야했다.

 

일단 이 문제의 정답 코드는

n = int(input())
m = int(input())
graph = [[]*n for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)


cnt = 0
visited = [0]*(n+1)

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


dfs(1)   
print(cnt)

 

 

일단 이차원 리스트를 이용해서 입력받은 그래프를 저장한다. 

 

 

이차원리스트는

 List Comprehension 방식으로 구현하였다. 

 

arr = [[0]*column for i in range(row)]

> 0이 column만큼 반복되고 그것이 row만큼 반복된다고 생각하면 된다.

c, r이 각각 2, 3 이라면

 

0 0

0 0

0 0 

이 되는 것이다. 

 

보통 이런 경우 i 대신 _로 많이쓴다. i 를 사용할 일이 없기때문이다.

 

이 문제의 예시에서 살펴보면

노드의 개수는 7개이다.

 

각 노드와 연결되어있는 노드를 저장하기위해 아래 사진과 같은 이차원 리스트를 만든것이다.

row는 1번부터 7번까지를 나타내기 위해 0번 index이므로 n+1을 하였고

 

column은 7번까지의 노드가 있으므로 7개를 만들었다. 

(6개도 가능하다!)

 

 

 

여기에서 m 만큼 for문을 돌면서 인접한 노드를 배열에 잘 넣어준다. 

 

++) 여기서는 append를 할것이기에 []*column 하지않고 그냥 []으로 해도 된다. 

arr = [[] for _ in range(row)]

 

 

 

---

 

for i in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

map(int, input().split()) 을 이용해 두 수의 입력을 받는 원리는 

 

 

 

이다. split() 으로 공백을 기준으로 두개의 요소로 나누고

map을 이용해 int 함수를 각 요소에 적용해서 수행한 결과 2개의 int 형 요소를 반환하는 것이다. 

 

 

 

이렇게 넣어진다. 

 

개수를 count할 변수 cnt를 선언해준다. 함수안에서 쓰기위해서는 global로 함수 내부에서도 선언해주어야한다.

해당 노드에 방문했는지 안했는지 저장하기위해 visited 배열을 만든다.

 

 

visited = [0]*(n+1)

0-idx이므로 1부터 호출하도록하기위해 n+1로 선언한다.

(7을 7으로 호출할 수 있다.)

 

 

이제 대망의 def 함수!

 

 def dfs(start) :
    global cnt
    visited[start] = 1  # start노드를 방문
    for i in graph[start] : #  start와 인접한 노드를 탐색
        if visited[i] == 0 : 
            dfs(i)
            cnt+=1

 

이제 여기서 1번 컴퓨터에서부터 시작한다고 하였으니

dfs(1) 을 하고 cnt를 출력하면 끝!!

 

 

 

🔑 그래서 어떻게 푸는데(정리)?

 

1. 컴퓨터간의 인접관계를 저장할 2차원 배열생성 & 저장

 

2. 개수를 저장할 cnt 변수 , 방문여부를 저장할 visited 리스트 생성

 

3. dfs 함수를 만들어 방문하지않은 컴퓨터는 바이러스를 전파하면서 cnt를 1증가하도록 

 

 

 

사실 그렇게 어렵지않은 문제인데 정말 정말 자세하게 적어보았다.

이 글을 많은 사람들이 볼지는 모르겠지만 파이썬 초급자에게는 이해하는데 많은 도움이 될것이다

 

 

 

그럼 이만..

 

내일 또 알고리즘 문제 풀어야지...

 

 

 

참고

 

https://wikidocs.net/13

02-2 문자열 자료형

http://pythonstudy.xyz/python/article/22-Python-Comprehension

예제로 배우는 파이썬 프로그래밍 - Python Comprehension

 

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."