교대최소제곱법
[코테준비] DFS 본문
DFS 깊이우선문제
sys를 import할 수 있다면 sys.setrecursionlimit(int(1e9))를 호출해야 에러가 안뜬다
사이클을 확인할때 사용
먹고 또 이동하고 먹고 또 이동하고를 나타낼때
그래프의 경우, 가중치 또는 특정 기준을 따라 탐색 방향의 우선순위를 결정한다
최대값 구할 때 "최대값보다 작으면" 이란 기준을 설정하고 찾는다
시간복잡도
N이 노드의 개수, E가 간선의 개수일 때
인접 리스트: O(N + E)
인접 행렬: O(N^2)
예제 풀이 프로세스
재귀함수를 사용
- 입력값 받기
- 방문여부를 남기는 그래프 만들기
- 탐색조건
- 시작점을 불러오고
- 방문했는지 여부확인하고 탐색
- not visited[][] and graph[][] == 1
- 탐색
- 일단 방문기록 남기고
- 4방향으로 움직인다
- 조건에 맞으면 재귀, 아니면 스탑
예제 문제
[백준 14500 : PYTHON] 테트로미노
문제 풀기 : 14500번 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두
cijbest.tistory.com
[DFS] 백준#19236: 청소년 상어/Python
📝 문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져
heytech.tistory.com
+DFS의 경우 재귀함수를 사용하기 때문에 DP로 풀리는지 고려해야함
'코딩테스트' 카테고리의 다른 글
| [코테준비] 순열, 조합, 백트래킹 (0) | 2023.09.11 |
|---|---|
| [코테준비] 분할정복, DP, 그리디 (0) | 2023.09.09 |
| [코테준비] 다익스트라 알고리즘, 벨만-포드 알고리즘 (0) | 2023.09.09 |
| [코테준비] BFS, 0-1 BFS (0) | 2023.09.09 |
| [코테준비] 시간 복잡도를 고려하자 (0) | 2023.09.09 |
'코딩테스트' Related Articles
more
