DFS & BFS

DFS

• Depth-First Search
• 그래프 완전 탐색 기법 중 하나
• 시작 노드에서 출발 → 한쪽 분기를 정하고 → 최대 깊이까지 탐색 → 이후 다른 분기로 이동하여 탐색
• 재귀 함수 or 스택 이용
• FILO 탐색
• 한 번 방문한 노드는 다시 방문 X → 방문 여부 체크 배열 필요

1. 시작할 노드를 정한 후, 사용할 자료구조 초기화
   • 인접 리스트로 그래프 생성
   • visit 배열 초기화, 시작 노드 방문 체크
   • 스택에 시작 노드 push
2. 스택에서 노드를 꺼낸 후, 노드의 인접 노드를 다시 스택에 삽입
   • 스택에서 노드를 pop → 탐색 순서에 기록
   • 꺼낸 노드의 인접 리스트를 참고 → 미방문 노드라면, 인접 노드를 스택에 삽입
   • 삽입한 인접 노드들의 방문 여부 체크
3. 스택이 비어있을 때까지 반복

DFS를 짜는 패턴
- 전염병, 바이러스 등에서 총 "몇개"의 노드를 감염시키냐는 DFS임
    - 모든 노드를 감염시키기 위한 "총 시간"을 물었으면 BFS (최단거리)
 

BFS

• Breadth-First-Search
• 시작 노드를 기준으로 → 가까운 노드를 먼저 방문
• FIFO 탐색 → 큐를 이용하여 구현
• 가까운 노드부터 탐색 → 목표 노드에 도착하는 경로가 여러 개일 때 → 최단 경로를 보장

1. 시작할 노드를 정한 후, 사용할 자료구조 초기화
   • 그래프 → 인접 리스트로 표현
   • visit 배열 초기화, 시작 노드 방문 체크
   • 탐색을 위하여 큐를 사용 → 시작점 push
2. 큐에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 모두 큐에 삽입
   • 큐에서 노드를 꺼내면서 → 탐색 순서에 꺼낸 노드를 기록
   • 꺼낸 노드의 인접 리스트를 참고 → 미방문 노드라면, 인접 노드들을 큐에 삽입
   • 삽입한 인접 노드들의 방문 여부 체크
3. 큐가 비어있을 때까지 반복

BFS를 짜는 패턴
- 우선 최단거리를 묻는 문제는 대부분 DFS임
- distance 배열과 visited 배열을 하나로 합쳐서 관리하면 좋음
    - visited를 [-1]로 초기화, 여기서 시작 노드 index 위치를 [0]으로 설정하면
    - visited, distance 모두 체크 가능
- queue.pop(), queue.appendleft()
   
1. 시작, 종점 입력
2. visited 배열, queue 초기화
3. visited 배열에 시작점 적용, queue 에 시작점 append
4. BFS 시작
    - 모든 노드를 "그냥 다 방문"이면 while queue: 로 조건을 잡으면 됨
    - "특정 종점까지 도달"이면 while visited[특정종점]==-1: 로 잡으면 됨
    4-1. queue.pop해서 cur에 저장
    4-2. 갈 수 있는 방향을 다 반복문 돌면서 확인
        - 새로운 위치를 nx라고 하면, nx=cur+dir[i]
        - nx가 유효한 범위(반드시 필요한 범위) 안에 있는지 체크, 아니라면 continue
        - position[nx]>0 이면 continue (이미 방문했거나, 방문 예정인 노드인지 체크)
	        - nx 유효 범위를 먼저 체크해야 nx index 위치의 position 을 방문할 때 out                of index 오류 안 남
	    - 위 조건 모두 충족했으면, <유효 범위 내> + <아직 방문 X> 이므로 queue.append
5. 최종적으로 최단거리를 출력
    - "그냥 다 방문" -> visited 배열을 돌면서 max 값 뽑고, 출력
    - "특정 종점" -> visited[특정종점] 출력