99클럽 코테 스터디 4일차 TIL : DFS(백준 24479번)
백준 24479번. 알고리즘 수업- 깊이우선탐색1(DFS)
⭐나의 풀이
🔎문제 정리)
N개 edge
M개 간선
모든 간선의 가중치 1
인접 정점은 오름차순으로방문
제한) 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)
예시1)
입력
5 5 1
1 4
1 2
2 3
2 4
3 4
출력
1
2
3
4
0
1. 시작지점 1에서 출발(1번 edge 방문)
2. 다음 순서인 2번노드를 시도하는데 1-2를 잇는 간선이 있고, 2를 방문하지 않았음을 확인한 다음 방문한다.
3. 2번과 같은 방식으로 3 edge 방문
4. 2번과 같은 방식으로 4 edge 방문
- 탐색 끝-
💡 아이디어)
1. DFS
- 간선정보를 저장하는 int형 2차배열 arr
- 방문여부를 저장하는 boolean형 1차 배열 visited(n번 노드의 방문여부를 visited[n]에 저장, 0 index사용x)
- 노드방문순서를 저장하는 int형 1차배열 answer(n번 노드의 방문순서를 answer[n]에 저장, 0 index 사용x)
- 노드 방문 순서를 누적시킬 int형 변수 cnt 사용 -> 전역변수로 선언함
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
/*
* 백준 24479번. 알고리즘 수업- 깊이우선탐색1(DFS)
* 날짜: 24-10-31
* 작성자: CSY
*/
private static int[][] arr; //간선정보
private static Boolean[] visited; //방문여부
private static int[] answer; //노드방문순서
private static int cnt=1; //노드방문순서
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
StringTokenizer st = new StringTokenizer(s);
int n = Integer.parseInt(st.nextToken()); //정점수<=100,000
int m = Integer.parseInt(st.nextToken()); //간선의 수<=200,000
int r = Integer.parseInt(st.nextToken()); //시작지점<=100,000
arr = new int[n+1][n+1];
visited = new Boolean[n+1];
answer = new int[n+1];
//간선정보 받아와서 배열에 저장
for(int i=0;i<m;i++) {
s = br.readLine();
st = new StringTokenizer(s);
int u = Integer.parseInt(st.nextToken()); //시작지점
int v = Integer.parseInt(st.nextToken()); //도착지점
arr[u][v] = 1;
arr[v][u] = 1;
}
StringBuilder sb = new StringBuilder();
dfs(answer, arr, r); //dfs 실행
for(int i=1;i<answer.length;i++) {
sb.append(answer[i]+"\n"); //방문순서를 출력
}
System.out.println(sb);
}
static void dfs(int[] V, int[][] E, int R) {
// V : 정점 집합, E : 간선 집합, R : 시작 정점
visited[R]=true; //R지점 방문
answer[R]=cnt; //현재 방문순서를 answer[R]에 저장
cnt++; //방문순서 ++1
for(int i=1;i<E[1].length;i++) {
if(E[R][i]==1) { //R번 edge의 간선정보를 담고있는 배열을 돌면서, i edge와 연결되있고)
if(visited[i]==null||visited[i]==false) { //i edge가 아직 방문안했다면
dfs(V,E,i); //i edge 방문
}
}
}
}
}
📌 결과
문제) "메모리 초과" 이슈 발생
개선) 메모리를 많이 차지하는 배열 대신, ArrayList를 사용하자.
설명) 코드에서 int형 2차배열 arr을 선언하고 n+1길이로 생성함(이 때, N<=100,000=10^5)
따라서, N=100,000이라고 가정하면
int형은 하나에 4byte이고 4byte*(10^5)*(10^5)= 4*10^10byte = 약 40GB 의 메모리를 차지한다.
하지만, 해당 문제에서의 메모리제한이 512MB 이기 때문에 배열은 사용할 수 없다.
따라서 인접리스트를 활용해보자.!!
인접 리스트 방식에서는 노드마다 인접한 노드를 담은 리스트가 필요하고,
각 리스트는 연결된 간선 수에 비례하여 메모리를 차지하기 때문에 총 메모리 사용량은 노드 수와 간선 수에 비례한다.
인접 리스트 방식에서 전체 메모리 사용량을 확인해보면, (4×n)+(8×m)으로 수렴된다.
참고) 인접 리스트의 메모리 사용량 분석
인접 리스트에서는 노드 수 n와 간선 수 m에 따라 메모리 사용량이 결정
- 노드 수 n: 각 노드는 자신만의 ArrayList를 가진다.
- 이 리스트는 노드당 4바이트의 참조(리스트의 주소)를 저장해야 한다.
- 따라서, 노드 n개에 대해 기본적으로 필요한 메모리는 4×n바이트이다.
- 간선 수 m: 각 간선이 두 노드 사이의 연결을 의미하므로, 인접 리스트 방식에서는 개의 간선 정보를 저장하기 위해 다음과 같은 메모리가 요구된다.
- 각 연결된 노드 번호를 저장하는 데 4바이트가 필요
- ArrayList에 저장되는 각 원소는 4바이트의 참조로 저장
- 따라서, 각 간선에 대해 총 바이트가 필요하다.
- m개의 간선이 있으므로 총 메모리 사용량은 8×m바이트가 된다.
예) 노드 수 n=100,000, 간선 수 m=200,000 인 경우
- 노드 수에 따른 메모리 사용량: 4×100,000=400,000바이트 (약 0.4MB)
- 간선 수에 따른 메모리 사용량: 8×200,000=1,600,000(약 1.6MB)
- 총 메모리 사용량: 0.4 MB+1.6 MB=2.0 MB
배열을 사용했을 때와 비교하면, 엄청난 메모리 감축 효과를 확인할 수 있다.
- 40GB(배열) -> 2MB(인접리스트)
✔ 최종 제출한 코드)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
/*
* 백준 24479번. 알고리즘 수업- 깊이우선탐색1(DFS)
* 날짜: 24-10-31
* 작성자: CSY
*/
private static List<Integer>[] arr; //간선정보
private static boolean[] visited; //방문여부
private static int[] answer; //노드방문순서
private static int cnt=1; //노드방문순서
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
StringTokenizer st = new StringTokenizer(s);
int n = Integer.parseInt(st.nextToken()); //정점수<=100,000
int m = Integer.parseInt(st.nextToken()); //간선의 수<=200,000
int r = Integer.parseInt(st.nextToken()); //시작지점<=100,000
arr = new ArrayList[n+1];
visited = new boolean[n+1];
answer = new int[n+1];
for(int i=1;i<n+1;i++) {
arr[i] = new ArrayList<>();
}
//간선정보 받아와서 list에 저장
for(int i=0;i<m;i++) {
s = br.readLine();
st = new StringTokenizer(s);
int u = Integer.parseInt(st.nextToken()); //시작지점
int v = Integer.parseInt(st.nextToken()); //도착지점
arr[u].add(v);
arr[v].add(u);
}
StringBuilder sb = new StringBuilder();
dfs(r);
for(int i=1;i<answer.length;i++) {
sb.append(answer[i]+"\n");
}
System.out.println(sb);
}
static void dfs(int R) {
visited[R]=true;
answer[R]=cnt;
cnt++;
Object[] newArr = arr[R].toArray();
Arrays.sort(newArr);
for(Object i: newArr) {
if(visited[(int)i]==false) {
dfs((int)i);
}
}
}
}
⭐오늘의 회고
✔ 메모리 제한
배열을 사용하는 것 보다 인접리스트를 사용할 시에 메모리 감축 효과를 볼 수 있다.!