그래프 완전 탐색 기법 중 하나

시작 노드에서 출발하여 탐색할 한 쪽 분기 정해서 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘

재귀 함수로 구현 = 스택 자료 구조(FIFO)이용 ⇒ 먼저 들어온 data가 나중에 나감 = 이게 재귀랑 로직이 같음

재귀 함수 이용하므로 stack overflow에 유의하긔

핵심 이론

• 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요
• 그래프는 인접 리스트(data를 담는 자료구조)로 표현
• 설명은 스택으로 하지만 코드는 재귀로 풀거임

1. DFS를 시작할 노드를 정한 후 사용할 자료구조(인접 리스트) 초기화하기
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
   1. 스택에서 노드를 꺼내면서 탐색 순서에 꺼낸 노드 기록
   2. 대상 노드의 인접 노드를 스택에 삽입(삽입 순서는 상관없음) 대신 이 인접 노드가 방문한 노드인지 아닌지는 꼭 확인하고 스택에 삽입해야 함 이미 방문한 노드는 skip
   3. 노드 삽입하며 방문 배열 체크
3. 스택 자료구조에 값이 없을 때까지 반복하기
   1. 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심

⇒ 즉, 스택에 노드를 삽입할 때 방문 배열을 체크하고 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하며 살펴봄

023 연결 요소 개수 구하기

• N이 1000이므로 N^2도 가능
• 연결 방향을 알려주지 않았음으로 양쪽으로 연결되어 있다는 뜻임
  • 방향이 없는 그래프이므로 양쪽 방향으로 엣지 모두 저장
• DFS가 돈 횟수 = 연결 요소 갯수

024 신기한 소수 찾기

• DFS 재귀 + 소수 판별로 문제 해결
• 자릿수마다 소수 검사를 반드시 수행
• 시간 복잡도는 제한된 깊이(최대 8)로 괜찮음
• 1자리 소수: 2, 3, 5, 7부터 시작해야 함

025 친구관계 파악하기

• DFS를 이용하여 깊이가 5가 되는 경로가 존재하는지 확인
  • 즉 친구 관계로 이어진 5명의 노드가 존재하는지 확인
• DFS 탐색 중 depth가 5가 되면 바로 종료 return
• 친구 관계는 양방향이므로 인접 리스트로 저장
• 시간 복잡도는 O(N + M)으로 충분히 가능

그래프를 완전 탐색하는 방법 중 하나

시작 노드에서 가까운 노드부터 탐색하는 방식

Queue (FIFO) 구조 사용

DFS와 달리 깊게 들어가지 않고 같은 레벨의 노드부터 탐색

방문 순서가 계층적 (Level Order) 으로 진행됨

최단 거리 탐색 문제에 유용

DFS는 재귀/스택, BFS는 큐 사용

동작 흐름

• 시작 노드를 큐에 삽입하고 방문 처리
• 큐가 빌 때까지 다음을 반복
  • 큐에서 노드를 꺼냄
  • 해당 노드와 연결된 방문하지 않은 모든 노드를 큐에 삽입
  • 이들을 방문 처리

026 DFS와 BFS 프로그램

• DFS (Depth-First Search)

  DFS(현재 노드) {
    방문 처리
    인접 노드들 중 방문 안 한 노드 → 재귀 호출
  }
  

  • 재귀로 구현
  • 번호가 작은 노드부터 탐색하기 위해 정렬 필요

• BFS (Breadth-First Search)

  BFS(시작 노드) {
    큐에 넣고 방문 처리
    큐가 빌 때까지 반복:
      - 큐에서 꺼낸 노드의 인접 노드들 중 방문 안 한 노드 → 큐에 넣기
  }
  

  • 큐로 구현 (LinkedList사용)
  • 정점 번호가 작은 순서대로 탐색하려면 인접 리스트 정렬 필요

027 미로 탐색하기

• BFS (너비 우선 탐색) 사용하여 최단 거리 구하기

• 왜? → DFS는 모든 경로를 탐색하므로 비효율적이고

  BFS는 한 칸씩 레벨 탐색 → 최단 경로에 적합

  • 시작점 (0,0)을 큐에 넣고 방문 처리
  • 큐에서 노드 꺼내고 상/하/좌/우 방향 탐색
  • 값이 1이고 아직 방문하지 않은 칸이면
    • 이동
    • 거리 누적 (현재위치 + 1)
    • 큐에 삽입

028 트리의 지름 구하기

1. 임의의 노드에서 BFS → 가장 먼 노드 A 찾기
2. A에서 다시 BFS → 가장 먼 노드 B까지의 거리 = 지름

이유: 트리에서 가장 먼 두 노드는 반드시 리프 노드끼리이며 한 번의 BFS로 루트에서 가장 먼 노드를 찾고 그 노드에서 다시 가장 먼 노드까지의 거리로 지름을 구할 수 있음

• 자료구조
  • 인접 리스트 사용 (ArrayList<Edge>[])
  • 각 노드에 연결된 노드와 거리 저장 → Edge(int to, int value)
  • 거리 저장 배열: distance[]

• 중앙값 인덱스 mid 계산

  mid = (start + end) / 2

• target과 mid 값 비교

  • 같으면 → 정답
  • 작으면 → 오른쪽 탐색 (start = mid + 1)
  • 크면 → 왼쪽 탐색 (end = mid - 1)

• 범위 내 반복 수행

• 값이 없으면 종료