관리 메뉴

차근차근

[백준 2606] 바이러스 본문

대학교/Algorithm

[백준 2606] 바이러스

SWKo 2020. 9. 8. 01:44

0. 제목

  • 백준 2606 바이러스
  • BOJ 2606 바이러스
  • 파이썬 2606 바이러스
  • Python 2606 바이러스

1. 문제

www.acmicpc.net/problem/2606

 

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어��

www.acmicpc.net


2. 풀이

  • adj라는 2차원 배열 형태를 선언한 후, 각 점의 연결 상태를 표시한다. adj[2] = [1, 3, 4] 라면 2번에 1번, 3번, 4번이 연결되어 있다는 것이다.
  • visited라는 1차원 배열을 선언한 후, 각 점에 대한 방문 여부를 표시한다. visited[3] = True 라면 3번 점에 이미 방문했다는 것을 의미한다.
  • 문제에서는 1번 점을 통해 탐색할 수 있는 점의 개수를 구하라고 하였고 dfs를 활용하면 된다.
  • 특정 점에서 출발하여 지나는 갯수를 셀 수 있는 함수를 만든다. 방문한 점에 대하여 visited[방문한 점] = True 를 수행하고, 인접한 점중 방문하지 않은 점에 대하여 재귀적으로 함수를 수행한다.
  • 전역변수로 선언한 count를 점을 방문할 때마다 1 증가시킴으로써 정답을 구한다.
  • 마지막에 시작점을 제외해야 하기 때문에 count에서 1을 뺀다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
= int(input())
= int(input())
 
adj = [[] for _ in range(n + 1)]
visited = [False* (n + 1)
count = 0
 
for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)
    
def dfs(now_pos):
    global count
    count += 1
    visited[now_pos] = True
    for next_pos in adj[now_pos]:
        if not visited[next_pos]:
            dfs(next_pos)
    
dfs(1)
print(count - 1)

 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1325] 효율적인 해킹  (0) 2020.09.09
[백준 1012] 유기농 배추  (0) 2020.09.08
[백준 1697] 숨바꼭질  (0) 2020.09.06
[백준 1260] DFS와 BFS  (0) 2020.09.05
[백준 2110] 공유기 설치  (0) 2020.09.04
0 Comments
댓글쓰기 폼