Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- react with typescript
- TypeScript
- Vue3
- 이클립스 DB연동
- 자바 for문
- 자바 향상된 for문
- 자바 while문
- 항해99
- 타입스크립트
- 자바 자동캐스팅
- 자바
- 항해99 2기
- java
- 자바 구구단 출력
- 자바 switch문
- 자바 조건문
- 자바 공배수
- 자바 삼항연산자
- 정보처리기사실기
- react ag grid
- 자바 public
- 프로그래머스
- 변수
- 자바 스캐너
- 자바 강제 캐스팅
- Til
- 자바 if문
- 조코딩
- 자바 반복문
- MySQL
Archives
- Today
- Total
뇌 채우기 공간
[백준] 2606 바이러스 파이썬 풀이(DFS와 BFS) 본문
문제
- 컴퓨터끼리 연결된 쌍이 주어진다.
- 1번 컴퓨터가 웜 바이러스에 걸렸을때 연결된 모든 컴퓨터가 웜 바이러스에 걸린다.
- 바이러스에 걸리는 컴퓨터의 수를 출력해라
문제풀이
- DFS로 푼다.
- 연결되어있는 노드를 끝까지 탐색해야하기 때문.
- 2차원 배열에 연결되어있는 값을 저장한다.
- 1번 노드에 연결된 모든 값을 visited_dfs에 저장하고 1번의 뺀 개수를 출력한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
# 정점의 연결정보 입력받기
n= int(input()) #정점
m = int(input()) #연결수
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited_dfs = []
def dfs(graph, cur_node, visited):
# 현재 노드를 방문처리
visited.append(cur_node)
graph[cur_node].sort()
# 현재 노드와 인접한 노드를 확인
for link_node in graph[cur_node]:
# 방문하지 않은 노드라면 재귀호출
if link_node not in visited:
dfs(graph, link_node, visited)
dfs(graph, 1, visited_dfs)
print(len(visited_dfs)-1)
|
cs |

그래프는 이렇게 출력된다.
1번이 2 번 5번이랑 연결되어있고
2번이 1 3 5랑 연결되어있고...

그리고 1번 노드와 연결되어있는 2 5를 확인하는데
2번이 visited에 없으니까 2번 노드를 방문하고 visited에 넣는다.
2번 노드와 연결되어있는 1 3 5를 확인하는데
1번은 visited에 있으니 넘어가고 3번을 방문하고 visited에 넣는다.
3번 노드와 연결되어있는 2번 노드를 확인하는데
2번은 visited에 있으니 넘어간다.
그럼 2번 노드와 연결되어있던 것 중에 5번을 확인한다.
.. 반복
728x90
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[백준] 11279 최대힙 파이썬 풀이 (힙) (0) | 2021.06.24 |
---|---|
[백준] 11399 ATM 파이썬 풀이 (그리디) (0) | 2021.06.24 |
[백준] 11047 동전0 파이썬 풀이 (그리디) (0) | 2021.06.24 |
[백준] 1541 잃어버린 괄호 파이썬 풀이 (그리디) (0) | 2021.06.24 |
[백준] 1002 피보나치 함수 파이썬 풀이 (동적계획법) (0) | 2021.06.24 |