DFS, BFS with Python
-
N X M 의 배열에서 N,M이 대개 10000~100000 사이의 범위
-
여러 개의 정점이 연결되어 있는 형태로 나올 때 활용
-
간선 개수가 작을 때는 DFS로 재귀함수 활용 가능 (or sys.setrecursionlimit() 설정)
-
간선 개수가 많을 떄는 BFS. 그래도 느리다면 백준 알고리즘 같은 경우 Pypy3 로 채점 시도 해볼 것
해당 문제
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
www.acmicpc.net
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. (
www.acmicpc.net
https://www.acmicpc.net/problem/1325
1325번: 효율적인 해킹
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.
www.acmicpc.net
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
www.acmicpc.net
'코딩테스트' 카테고리의 다른 글
| 알고리즘 풀이 블로그 (0) | 2020.07.15 |
|---|---|
| 코딩인터뷰완전분석 - 알고리즘 설계의 5가지 접근법 (0) | 2020.06.12 |
| 백트래킹, N Queen (0) | 2020.02.17 |
| DP (0) | 2020.01.17 |
| 코테 에러 분석 (0) | 2020.01.07 |