자바 알고리즘 기본 개념 익히기(7)-DFS & BFS

알고리즘 활용 마스터 가이드

상황 (문제의 질문)	추천 알고리즘	핵심 도구	이유
"최단 거리/가장 빠른 시간"	BFS (너비 우선)	Queue, visited[][], dr/dc	파동처럼 퍼져나가서 도착점을 가장 먼저 밟는 놈이 정답이기 때문!
"모든 경우의 수 다 찾기"	DFS (깊이 우선)	재귀(Recursion), visited[]	한 우물만 끝까지 파는 성격이라, 모든 경로를 하나씩 훑어보기 좋음.
"이 섬이 총 몇 개지?"	둘 다 가능 (보통 DFS)	visited[][], 4방향 탐색	연결된 덩어리 하나를 끝까지 다 색칠해서 "한 덩어리 끝!"이라고 체크하기 쉬움.
"가중치가 다른 최단 거리"	다익스트라	PriorityQueue	핑크색 필기에 있던 놈! 길이 막히거나 뚫린 정도가 다를 때 쓰는 고급 기술.
"미로/격자판 이동"	BFS	nr = r + dr[i]	조이스틱(dr, dc)을 써서 상하좌우 한 칸씩 이동할 때 가장 표준적임.

1. BFS (너비 우선 탐색)

• 언제 써? 최단 거리, 미로 탈출, 최단 시간.
• 이거 없으면 안 돼! Queue, visited 체크 (큐에 넣을 때 체크!).
• 비유: 호수에 던진 돌의 파동. 가장 먼저 닿는 파동이 최단 거리!

2. DFS (깊이 우선 탐색)

• 언제 써? 갈 수 있는 모든 경로를 확인해야 할 때, 재귀함수 공부할 때.
• 이거 없으면 안 돼! 재귀함수 호출, 종료 조건(안 쓰면 무한 루프!).
• 비유: 미로에서 한쪽 벽만 짚고 끝까지 가보기. 막히면 되돌아오기.

3. 인접 행렬 vs 인접 리스트

• 인접 행렬 (map[N][N]): 정점이 적을 때(1,000개 이하) 쓰기 편함. 서희님이 오늘 푼 미로 문제가 이거!
• 인접 리스트 (ArrayList<Integer>[]): 정점이 엄청 많을 때 메모리를 아끼려고 씀. (나중에 배우게 될 거예요!)