DFS BFS 핵심 설명 (중요)

RostoryT·2022년 5월 23일

BFS BFS 최단경로 BFS 팁 DFS DFS BFS 문제 유형 DFS BFS 차이 DFS 팁

Brave Python

목록 보기

3/7

용감한 파이썬 - DFS BFS란?

링크 : https://covenant.tistory.com/132

내가 정리한 DFS BFS 개요

동빈나 뼈대 코드 링크 : https://velog.io/@taehyeon96/3.-%EC%9D%B4%EC%BD%94%ED%85%8C-DFS-BFS-%EA%B0%9C%EC%9A%94-%EB%A9%94%EC%9D%B8-%EC%BD%94%EB%93%9C

## DFS BFS 알아둘 것
* DFS 문제든 BFS 문제든 방문 기록을 활용하는 방식으로,
  "방문 기록"을 남기는 방향으로 문제를 푸는 유형이다 라고 생각하면 될거같다. 

-----------------------------------------------------------------------------------------
## 항상 알아둘것
* DFS할 때 조건을 거는데, break조건은 특이사항 아니면 거의 없다!!!
* 이번 문제에서도 사방면으로 이동한 경우를 다 봐야 하니까 break말고 continue를 써야한다!
* if문 끝나면 알아서 재귀 끝날거임(0이나 visit=False 만 남은 경우에)
* **그리고 DFS BFS 코드의 큰 틀은 항상 똑같음!!! 나중에 내가 푼거 다시 볼 때 길다고 겁먹거나 대충보지 말기!!**

-----------------------------------------------------------------------------------------
## 다 필요없고 BFS 핵심

0. BFS는 재귀 X이다.
1. 따라서 BFS 안에 큐 생성한다
2. 시작 포인트 일단 넣는다

3. while queue
4.    현위치 = popleft()
5.    for 다음위치(또는 다음 노드) 가져와
6.        다음 위치가 조건에 맞으면(또는 방문 안했으면) 이동시켜
7.        queue.append(다음위치)   <--- 개중요 (for안에 넣어서 다음위치/이웃노드 전부 넣어주는)

-----------------------------------------------------------------------------------------
* 그리고 DFS 문제든 BFS 문제든 방문 기록을 활용하는 방식으로,
* "방문 기록"을 남기는 방향으로 문제를 푸는 유형이다 라고 생각하면 될거같다.

## DFS 또는 BFS n x m 주의사항
* 항상 n x m 행렬 문제는 dy, dx 이거 써서 다음 위치일 때 dfs() 수행하는거다
* 큰 틀은 항상 똑같다!!!!!!!!!!!!!!!!!!!!!!!!!!!
* 시작점은 brute force로 전부 넣어주는거다!!!!!!!! => **단 방문하지 않은 노드만!!**

deque 모듈 안쓰면 시간복잡도 박살남

그리고 pop(0)이 시간복잡도가 O(n)이고, popleft()가 O(1)이라고 함

=> 왼쪽에서 바로 빼면 되는데, pop()은 끝까지 다 보고 0인 것을 찾아야 하니까!!

(중요) DFS, BFS 시 순회 + 순회했던 노드들의 넓이 저장 방법

DFS 순회 유형 총망라 종합본 (백준 2667)
- https://velog.io/@taehyeon96/백준2667-단지번호붙이기DFS-순회문제-순회-종합본
실제 사례 : NHN 공개 기출문제 (순회 유형 총망라 종합본)
- https://velog.io/@taehyeon96/비공개-포스트NHN-홈페이지-공식-기출Pre-Test-1차-DFS-순회-DFS-너비-체크

BFS 순회가 아닌 문제 + 최단경로는 BFS (이거 중요)

내가 지금까지 한건 시작점이 하나인 경우에만 BFS인데
해당 문제는 시작점이 두 개 이상인 경우의 BFS임
- 최단경로 구하기 문제에서도 사용된다고 함
시작 토마토 위치를 전부 Queue에 넣어준 후에 BFS를 수행하는 것이다
- 지금까지 공부한 방식은 시작 토마토 위치 하나만 넣어주고
- 걔가 끝나면 걔 주변의 위치를 파악해서 하는 것이었으나
- 시작 위치를 처음부터 que에 넣어주고 que(A, B)
  - 시작점 A의 이웃 다 넣어준 후 que(B, a, b, c)
  - A의 이웃인 a의 이웃들을 수행하는게 아니라,
  - 시작점 B의 이웃 먼저 다 넣어주고 A의 이웃인 a를 수행 que(a, b, c, x, y, z)

최단경로 방법
- 방문을 했냐 안했냐 (X)
- 이동할 때마다 값을 갱신 (graph[ny][nx] = graph[prev_y][prev_x] + 1)
- 이때, 마지막 출력에서 -1을 해줘야 할수도 있다! (이동후 = 이전거 + 1 이므로)
- 유형 1 - 최소 몇 번만에 이동할 수 있는가
  - 백준 1697 숨바꼭질 문제 (중요)
    : https://velog.io/@taehyeon96/백준1697-숨바꼭질DFS-BFS
  - 백준 7562 나이트의 이동 문제 (중요)
    : https://velog.io/@taehyeon96/백준7562-나이트의-이동BFS-최단경로중요
- 유형 2 - 시작점 2개 이상
  - 백준 7576 (토마토 문제)
    : https://velog.io/@taehyeon96/백준7576-토마토BFS-순회문제

1차원 배열의 BFS 최단거리

중요 내용
- 1차원 배열의 BFS의 경우,
  - 동빈나가 알려준대로 메모이제이션 해도 되지만
  - 메모리 초과 error가 발생할 수 있음
- 이 문제 솔루션처럼
  - [계산한 값, cnt] 묶어서 진행해
  - 다음 진행 시 [다음 계산한 값, cnt += 1]
  - 이 문제의 경우엔 앞으로 나아가는 (오른쪽으로만 가는) 경우였긴 했음
관련 문제 (백준 16953) : https://velog.io/@taehyeon96/백준16953-A-BDFS-BFS

매우매우매우 중요 포인트 팁

DFS 끝까지 갈 때 주로 사용
DFS 특정 영역/깊이까지 가고싶을 때 임의 깊이를 정하거나,
구분되는 영역(예를들어 바다 위의 빙산 / 섬 / 그래프 몇 개? 구분) 이런 문제에서
DFS 1회 수행 = 1개 빙산 / 섬 / 그래프

DFS BFS 문제적 접근으로 차이 한번 읽어보기 : https://foameraserblue.tistory.com/188?category=481823
DFS BFS 기본 문제추천 링크 : https://covenant.tistory.com/132
DFS BFS 거침없는 문제추천 링크 : https://covenant.tistory.com/147

갑자기 생각난거
민준 LG전자 3번째 문제 -> 빙산 구분하기에서
땅의 고도는 1 ~ 9까지임, 섬이 2개가 되는 경계를 찾아라
ex) 물이 1까지 차면 2~9는 땅, 1은 바다 경계
  	물이 3까지 차면 4~9는 땅(=섬이 될 수도), 1~2는 바다, 3은 경계

def dfs():
	DFS 수행
    
def main():
	빙산 개수 저장하는 변수 = 0
    

	for _ in range(고도의 최고점(=9)):  # 수면 아래서부터 하나씩 올라간다
        for _ in range(len(graph)):   # 땅은 전부 풀서치	
			if