DFS & BFS

Pattern

BFS
- 번지기 문제 (불, 부패, 오염, 바이러스 등)
	-> 주어지는 각 위치를 queue에 추가하고 BFS 시작
	-> 만약 이동하는 대상이 둘일 때, 서로 독립적 움직임일 때
		-> 하나를 끝까지 BFS 돌리고, 이 값을 비교하면서 다른 하나 BFS 진행
	  
- 뭉쳐있는 덩어리의 개수를 세는 문제 (뭉쳐있는 구역의 개수 세기)
	-> (0,0)부터 끝까지 queue에 append하는 식으로 진행
		-> 근데 방문 X, 덩어리의 각 개체가 존재하는 위치만 queue에 append
	-> 이후 BFS 돌리고, 각 while이 끝날 때마다 개수+1 해주면 총 덩어리 개수 나옴
	
- State BFS (벽 부수기 최단거리 등)
	-> 벽을 중간에 부수면서 이동한 경로, 벽을 안 부수면서 이동한 경로를 구분해야 함
	-> queue에, 중간에 벽을 부쉈는지의 flag 값을 추가, (x,y,0or1)를 append
	-> (cx,cy,flag)에서,
		-> (nx,ny)가 벽이 아니면 현재 flag를 따라서 진행
		-> (nx,ny)가 벽이고, 아직 flag가 0이라면 벽 부수기 실행, flag+=1
	-> 중요한 점: 그럼 벽을 부순 경로와 안 부순 경로 중에 뭐가 더 최단거리인지?
		-> 어차피 BFS는 먼저 목표에 도달한 경로가 최단거리임 (이게 중요)
		-> 따라서 그 경로가 뭐든 간에 먼저 (n-1, m-1)에 도달하면 종료
	

DFS

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

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

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[특정종점] 출력