문제 : https://www.acmicpc.net/problem/24479
- Q) 오름차순 깊이우선 탐색 구현
🚨오늘의 학습
⭐️DFS(깊이우선탐색)⭐️
깊이 우선 탐색(Depth First Search, DFS)은 그래프 또는 트리에서 한 노드에서 출발하여 최대한 깊이 내려간 후, 더 이상 갈 곳이 없으면 돌아와 다른 경로를 탐색하는 방식의 탐색 알고리즘입니다
🥊🥊🥊🥊🥊🥊한놈만 팬다🥊🥊🥊🥊🥊🥊🥊
⭐️그래프⭐️ - 네트워크, 지도
- 그래프는 여러 개의 노드(또는 정점)와 이 노드들을 연결하는 간선으로 구성됩니다.
※ 간선 = 노드 -1(모든 노드가 반드시 연결되어 있을 필요는 없다.)- 사이클 존재 가능(시작 노드로 되돌아 온다)
- 방향 그래프(Directed Graph) / 무방향 그래프(Undirected Graph)
- 그래프는 노드들이 하나의 덩어리로 연결되지 않고, 여러 개의 연결된 컴포넌트(Component)로 구성될 수 있습니다.
A --- B | | C --- D --- E ==================================== A ← B ↓ ↑ C ⇄ D → E
⭐️트리⭐️
- 계층 구조: 트리는 계층적(Hierarchical) 구조를 가지며, 노드들이 부모-자식 관계로 연결됩니다.
- 사이클 없음
- 트리에는 루트(Root)라 불리는 시작 노드가 있으며, 모든 자식 노드는 단 하나의 부모 노드만 가질 수 있습니다. (자식노드를 최대 2개를 갖게 되면 이진트리)
- 트리는 모든 노드가 하나의 덩어리로 연결되어 있어야 하며, 연결 그래프의 특성을 가집니다.
⭐️재귀함수⭐️ - 후입선출
- 재귀 함수는 내부적으로 함수 호출 스택을 사용하여 호출된 함수의 이전 상태를 저장합니다.
- 각 함수 호출이 새로운 노드를 방문하는 역할을 하고, 더 이상 방문할 노드가 없으면 함수가 종료되면서 자동으로 이전 호출로 돌아갑니다.
- DFS의 후입선출 구조구현 가능
⭐️스택⭐️ - 후입선출
- 스택에 방문 노드를 저장해 두었다가, 더 이상 방문할 노드가 없으면 스택에서 꺼내어 이전 노드로 돌아갑니다.
- DFS의 후입선출 구조구현 가능
🗝️ 1. 첫번째 시도
- 노드의 연결을 int[][] 이차원 배열로 구현
- 서로 연결된 노드외 연결되지 않은 노드도 메모리에 저장
그 결과 시간초과 발생 🅾️
🗝️ 2. 두번째 시도
- int[][] → ArrayList<ArrayList> (인접리스트)
- 서로 연결된 노드들만 메모리에 저장해 메모리 절약
시간 초과 발생 ❎
// 재귀함수
public static void dfs(int i){
visited[i]=step;
step++;
for(int j : graph.get(i)){
if(visited[j]==0){
dfs(j);
}
}
}import java.io.*;
import java.util.*;
public class Main {
static int[] visited;
static int edge = 0;
static int node = 0;
static int startNode = 0;
static ArrayList<ArrayList<Integer>> graph; // 인접 리스트
static int step = 1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
edge = Integer.parseInt(st.nextToken());
node = Integer.parseInt(st.nextToken());
startNode = Integer.parseInt(st.nextToken());
visited = new int[edge+1];
graph = new ArrayList<>(edge + 1);
for (int i = 0; i <= edge; i++) {
graph.add(new ArrayList<>());
}
// 인접리스트 생성
for (int i = 0; i < node; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph.get(start).add(end);
graph.get(end).add(start);
}
// 인접 리스트 정렬 (오름차순 방문)
for (int i = 1; i <= edge; i++) {
// 오름차순 정렬
Collections.sort(graph.get(i));
}
dfs(startNode);
for(int i = 1; i<=edge; i++){
System.out.println(visited[i]);
}
}
with me