[Do it! 알고리즘 코딩 테스트 자바] BFS 너비 우선 탐색 - 백준 1260(11일차)

BFS (너비 우선 탐색)

• 정의: 시작 정점에서 가장 가까운 정점부터 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 그래프 탐색 알고리즘.
• 핵심 원리:
  • 선입선출(FIFO) 방식의 큐(Queue) 자료구조 활용.
  • 현재 노드와 인접한 모든 미방문 노드를 큐에 삽입하며 레벨 단위로 탐색 진행.
  • 중복 탐색을 막기 위해 노드를 큐에 삽입하기 직전(혹은 직후) 방문(visited) 여부 체크 필수.

DFS와 BFS의 차이점

• 탐색 방식: DFS는 한 우물을 끝까지 파고드는 방식(깊이 우선), BFS는 얕고 넓게 모든 방향을 고르게 탐색하는 방식(너비 우선).
• 자료구조: DFS는 스택(Stack) 또는 재귀 호출 사용, BFS는 큐(Queue) 사용.
• 주요 용도: DFS는 모든 경로 탐색, 백트래킹, 사이클 판별에 유리함. BFS는 최단 거리(가중치가 1일 때), 최소 횟수 찾기 등에 유리함.
• 방문 처리 시점: DFS는 해당 노드를 방문(재귀 진입)했을 때 처리, BFS는 큐에 넣을 때 방문 처리하여 중복 삽입 방지.

---

[1260번: DFS와 BFS]

• 고려 내용: 하나의 그래프를 DFS와 BFS로 각각 탐색하고 결과를 출력하는 방법. 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것부터 방문하기 위한 사전 정렬 작업.
• 문제 핵심: 각 알고리즘에 맞는 자료구조(재귀/큐)의 정확한 활용 및 방문 체크(visited) 배열의 초기화와 적용 시점 이해.
• 최적화 및 고려사항:
  • 비효율적인 BFS 설계: 큐와 반복문을 쓰지 않고 재귀를 이용해 BFS를 구현하려다 탐색 순서가 꼬이고 무한 루프 발생 가능성 존재. -> 큐(Queue) 자료구조 도입: while(!queue.isEmpty()) 구조를 사용하여 표준적인 너비 우선 탐색 로직 구현.
  • 방문 처리 시점 지연: 큐에서 노드를 꺼낼 때(poll) 방문 처리를 하면 큐에 동일한 노드가 중복으로 들어가는 메모리, 시간 낭비 발생. -> 삽입 시점 방문 처리: 인접 노드를 탐색하고 큐에 삽입하는 순간(queue.add(next)) 즉시 방문 처리(visited[next] = true)하여 중복 방지.
  • 부정확한 결과 저장 방식: 고정 길이 배열(int[] BFS_result = new int[S])에 결과를 저장하고 순회 출력 시, 미방문 정점의 빈자리(0)까지 출력되어 오답 처리됨. -> 동적 결과 저장 체계: 탐색 즉시 StringBuilder나 ArrayList에 노드 번호를 기록하여, 방문한 노드만 정확한 순서대로 출력하도록 메모리 및 출력 방식 최적화.