DFS

깊이 우선탐색은 그래프나 트리에서 한 방향으로 갈수있는 곳 까지 끝가지 탐색해보고,

더 이상 갈 곳이 없으면 뒤로 돌아와서 다른 길을 찾는 알고리즘

🐥필수 준비물 2가지

1. 방문 기록부(visited 배열) : 한번 방문한 노드를 다시 방문 하지 않도록 체크
2. 인접 리스트 : 각 노드에서 어느 노드로 이동 할 수있는지 정도를 저장

⚙️DFS의 핵심 동작 순서

1. 현재 노드 방문 처리: visited[now] = true;
2. 현재 노드 출력 / 처리: 필요하다면 현재 노드 번호를 출력하거나 정답 변수에 계산을 수행함
3. 인접 노드 확인: 현재 노드와 연결된 다른 노드들을 하나씩 살펴보기
4. 조건부 재귀 호출 : 인접노드가 아직 방문하지 않았다면(!visited[next])
   1. 그 노드를 대상으로 다시 DFS 함수 재귀호출( 더 깊이 들어감)

🔎DFS 대표적인 유형

1. 연결된 덩어리 찾기 : 섬이 몇개인가?, 아파트 단지가 몇 개인가?
   1. 동작방식: 지도를 훑다가 섬(1)을 발견하면 그지점에서 DFS를 시작 상하좌우 연결된 모든 섬을 다 방문 할 때까지 깊게 들어감
   2. 핵심 : 한번의 DFS가 끝나면 덩어리 1개를 찾은 것, 방문 체크를 확실히해서 중복을 막아야함
2. 모든 경우의 수 탐색(백트래킹): 모든 갈림길을 다 가보되, 조건에 안맞으면 돌아오는 상황
   1. 동작 방식: 1번칸에 숫자를 놓고, 2번칸에 숫자를 놓고.. 끝까지 가보고 만약 끝(리프노드)에 도달 했는데 정답이 아니라면 바로 전 단계로 돌아와서 다른 숫자를 놓아봅니다
   2. 핵심 : 재귀 함수를 호출 하기 전에 전 후로 상태를 복구하는 과정
3. 경로의 특징을 저장 해야할 때: A에서 B지점으로 가는 경로 중에 특정 조건을 만족하는 경로가 있는가?
   1. 동작방식 : 지금 내가 지나온 경로를 스택에 담고 있다
   2. 핵심 : 경로마다 점수가 있거나, 특정 지점을 반드시 거쳐야 하는 등의 제약조건이 복잡 할때
4. 트리 구조의 순회 : 데이터가 계층형( 부모, 자식)으로 되어있을때, 가장 밑바닥까지 내려가서 정보를 수집해 올라오는 경우
   1. 동작 방식: 자식 노드들의 값을 다 더해서 부모 노드에게 전달하는 식의 상향식 계산이 필요할 때 유용
   2. 핵심 : 재귀의 반환 값을 활용하여 바텀 업으로 정보를 전달

🥊격자 문제 테크닉

• 상하좌우 방향 배열( dx, dy 테크닉)
  • 격자문제의 핵심은 현재좌표에서 인접한 칸으로 이동 하는 것
   
  • dx = {-1, 1, 0, 0} : 행의 변화량(위 아래)
  • dy = {0, 0, -1, 1} : 열의 변화량(왼쪽, 오른쪽)
  • 사용법 : for문을 4번 돌리면서 nx = x + dx[i], ny = y + dy[i]를 구함
• 경계 검사
  1. 새로운 좌표 (nx, ny)를 구했다면, 그 좌표가 지도의 범위 안에 있는지 반드시 확인 해야함
     1. 조건식 : 보통 다음과 같은 조건을 체크0 ≤ ny < N(열의 범위)
     2. 0 ≤ nx < N(행의 범위)
     이 조건은 보통 if 문의 가장 처음에 위치 시켜서, 범위 밖일 경우 바로 continue 시키는 것이 깔금
• 입력 처리
  1. 2667번(아파트 단지번호) 처럼 01101 처럼 공백없이 들어올 경우
     1. br.readLine으로 한줄 통채로 받고 line.charAt(j) - '0'을 사용하여 문자를 숫자로 변환합니다.
     2. String[] row = br.readLine().split(""); 로 하거나
• 전체 탐색과 단지별 탐색의 분리(격자 문제에서 ‘덩어리’를 찾을 때는 이중 루프와 DFS의 역할분담이 중요하다
  1. 이중루프 : 지도의 모든 칸을 하나씩 확인 합니다
     1. 여기에 집이 잇고, 아직 방문을 안했네?? 라고 발견하면 DFS 호출
     2. 이 지점이 단지의 시작 점임

면접 질문

• DFS와 BFS의 차이점을 설명하고 각각 어떤 상황에서 사용하는 것이 유리한가?

BFS는 인접 노드 부터 넓게 탐색하며 큐를 사용하고 최단경로를 찾을때 유리하다

DFS는 미로에서 한우물만 파는 느낌이고 BFS는 물결이 퍼져나가는 느낌이다

DFS는 한 경로를 끝까지 탐색하고 재귀나 스택을 사용해서 모든노드를 방문해야 하거나 경로의 특징(제약)이 있는 경우를 저장할때 유리하다

• DFS 시공간 복잡도는 어떻게 되나?

공간 복잡도는 방문 배열과 재귀 호출 스택이 필요 하므로 O(V)입니다

최악의 경우(일렬로 연결된 그래프) 스택의 깊이가 노드의 개수만큼 깊이가 길어질 수 있다

시간복잡도는 노드의 개수를 V, 간선의 개수를 E라고 할때, 인접리스트로 구현하면 O(V+E) 입니다 모든 정점과 간선을 한번씩 확인하기 때문입니다.(인접행렬은 O(V^2) )

• DFS를 재귀로 구현 할때 발생할 수 있는 문제점과 해결방안은?

그런데 자바의 경우는 JVM의 기본 스택 사이즈가 제한 적이기 때문이다

해결방안: 재귀 대신 명시적인 스택 자료 구조를 사용하는 반복문 방식의 DFS로 구현하거나 문제의 조건에 따라 BFS를 고려해 볼 수 있다

문제점은 노드의 개수가 많아지면(깊이가 깊어지면) 스택오버플로우가 발생 할 수 있다.

• 그래프에서 사이클이 있는지 확인 하려면 어떻게 해야 할까여?

DFS를 사용할 것 같습니다 왜냐하면 탐색과정에서 현재 탐색중인 경로(스택에 들어있는 노드들)에 이미 있는 노드를 다시 만나게 된다면 사이클이 존재한다고 판단 할 수 있다

• 아주 넓고 얇은 트리와 아주 좁고 깊은 트리 중 DFS가 더 효율 적인 경우는 언제인가요

반대로 최단 거리를 찾는 문제라면 트리의 모양과 상관없이 BFS가 유리합니다

넓고 얇은 트리가 더 효율적일 가능성이 높습니다 트리가 너무 깊으면 DFS는 스택 메모리를 많이 사용하고 정답을 찾는데 시간이 오래 걸릴 수 있지만 넓고 얖으면 금방 바닥을 찍고 돌아오기 때문입니다

• DFS에서 visited 배열을 사용하지 않으면 어떤일이 벌어질까요?

방문 처리를 하지 않으면 사이클이 존재하는 그래프에서 무한 루프에 빠지게 됩니다. 이는 결국 스택 오버플로우를 발생시켜 프로그램이 비정상 종료되는 원인이 됩니다. 따라서 DFS의 정당성과 효율성을 보장하기 위해 visited 배열을 통한 방문 체크는 필수적입니다.