⚒ 자료구조 스터디 ⚒
📂DFS
✅DFS란
- Depth First Search의 약자이며, 깊이 우선 탐색이라고 불린다.
- 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다.
❓어디서 쓰나요❓
- 백트래킹 (모든 경우의 수를 전부 고려하는 알고리즘)
- 자동 미로 생성
📂DFS
❗스택 오버플로우에 유의해야 한다.
✅구현
- 보통 재귀호출을 이용해 구현한다.
- 단순한 스택 배열로도 구현하기도 한다.
🔎 장점
1. 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다.
2. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
🔎 단점
1. 해가 없는 경로에 깊이 빠질 가능성이 있다.
2. 얻어진 해가 최단 경로가 된다는 보장이 없다.
❓스택 오버플로우란❓
Stack Overflow는 Stack 영역의 메모리가 지정된 범위를 넘어갈 때 발생한다.함수에서 지역 변수를 선언하면 지역 변수는 Stack 메모리에 할당되고 함수를 빠져나오면 Stack 메모리에서 해제된다.
만약 한 함수에서 너무 큰 지역 변수를 선언하거나 함수를 재귀적으로 무한정 호출하게 되면 stack overflow가 발생할 수 있다.
📐문제풀이
🚩백준: 실버3 - Q2606 바이러스
문제
Q. 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다.
컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.
둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.
이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
예시
🔻 입력값 🔻
7
6
1 2
2 3
1 5
5 2
5 6
4 7
🔻 출력값 🔻
4
✅백준 - Q2606 문제풀이
🎯 처음 구상도
1. 인접리스트를 이용해서 DFS를 구현한다.
2. 방문하지 않은 곳을 제외해서 카운트를 한다.
3. 출력한다
❓1번 컴퓨터를 포함해서 카운트를 해서 틀렸었다..
💻결과 코드
public class Silver3_Q2606 {
static List<Integer>[] Node;
static int[] visit;
static int visitNode = 1;
public static void main(String[] args) throws IOException {
int count = 0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
Node = new ArrayList[N+1];
visit = new int[N+1];
for (int i = 1; i <= N; i++){
Node[i] = new ArrayList<>();
}
while (M > 0){
st = new StringTokenizer(br.readLine(), " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
Node[A].add(B);
Node[B].add(A);
M--;
}
for (int i = 1; i <= N; i++) {
Collections.sort(Node[i]);
}
dfs(1);
for (int i = 1; i <= N; i++){
// 1번 노트일때를 제외함
if (visit[i] != 0 && visit[i] != 1){
count++;
}
}
System.out.println(count);
}
static void dfs(int N){
visit[N] = visitNode++;
for (int next : Node[N]){
if (visit[next] == 0){
dfs(next);
}
}
}
}
🚩백준: 실버2 - Q24479 알고리즘 수업 - 깊이 우선 탐색 1
문제
입력
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.
다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.
출력
첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다.
i번째 줄에는 정점 i의 방문 순서를 출력한다.시작 정점의 방문 순서는 1이다.
시작 정점에서 방문할 수 없는 경우 0을 출력한다.
🔻입력 예시🔻
5 5 1
1 4
1 2
2 3
2 4
3 4
🔻출력 예시🔻
1
2
3
4
0
🔻입력 예시2🔻
2
✅백준 - Q24479 문제풀이
🎯 처음 구상도
1. 인접행렬을 통해서 DFS 구현
2. 방문 순서를 담을 int형 배열 생성
3. 방문시 static으로 존재하는 순서에++
❓ 메모리 초과 오류 발생
❌ 실패 이유 분석
인접행렬의 공간 복잡도는 O(V^2)로 메모리가 초과됐다.
⭕ 해결
인접리스트로 바꿔서 공간 복잡도를 O(V + E)로 줄여 메모리 초과를 해결.
💻결과 코드
public class Silver2_Q24479 {
static List<Integer>[] Node;
// 원래는 이렇게 해서 방문 기록을 했는데, 기본적으로 방문하지 않은 곳은 0으로 해야하기 때문에 타입을 변경
// int는 자동으로 0으로 초기화됨
// static boolean[] visit;
static int[] visit;
static int visitNode = 1;
// 이렇게 되면 빌더가 필요 없어짐
// static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
Node = new ArrayList[N+1];
visit = new int[N+1];
for (int i = 1; i <= N; i++) {
Node[i] = new ArrayList<>();
}
while (M > 0){
st = new StringTokenizer(br.readLine(), " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
Node[A].add(B);
Node[B].add(A);
M--;
}
// 원래 stream을 사용해서 dfs에서 하려고 했으나, 백준은 자바 11을 사용해서 안되는듯..
for (int i = 1; i <= N; i++){
Collections.sort(Node[i]);
}
dfs(R);
// sb.append(0);
// System.out.print(sb);
// 노드 최대 출력을 <로 해놔서 실패
for (int i = 1; i <= N; i++){
System.out.println(visit[i]);
}
// System.out.println(sb);
}
static void dfs(int N){
// 방문순서 저장
visit[N] = visitNode++;
// sb.append(N).append("\n");
// 정렬 두 가지 방법 시도..
// Node[N].stream().sorted().collect(Collectors.toList())
// Node[N].stream().sorted().toList()
for (int next : Node[N]){
if (visit[next] == 0){
dfs(next);
}
}
}
// === 기존 코드 === //
// static boolean[][] Node;
// static boolean[] visit;
// static StringBuilder sb = new StringBuilder();
//
// public static void main(String[] args) throws IOException {
//
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// StringTokenizer st = new StringTokenizer(br.readLine(), " ");
//
//
// int N = Integer.parseInt(st.nextToken());
// int M = Integer.parseInt(st.nextToken());
// int R = Integer.parseInt(st.nextToken());
//
// Node = new boolean[N+1][N+1];
// visit = new boolean[N+1];
//
// while (M > 0){
// int A = Integer.parseInt(st.nextToken());
// int B = Integer.parseInt(st.nextToken());
//
// Node[A][B] = true;
// Node[B][A] = true;
// M--;
// }
//
// dfs(R);
// sb.append(0);
// System.out.println(sb);
//
// }
//
// static void dfs(int N){
// visit[N] = true;
//
// for (int i = 1; i < Node.length; i++){
//
// if (Node[N][i] && !visit[i]){
// visit[i] = true;
// sb.append(i).append("\n");
//
// dfs(i);
// }
// }
// }
}
🚩백준: 실버2 - Q11724 연결 요소의 개수
문제
Q. 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
위의 경우에는 연결요소가 2개 (연결되어 있는 집합의 갯수)
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
출력
첫째 줄에 연결 요소의 개수를 출력한다.
예시
🔻 입력값 🔻
7
6
1 2
2 3
1 5
5 2
5 6
4 7
🔻 출력값 🔻
4
✅백준 - Q2606 문제풀이
🎯 처음 구상도
1. 인접리스트를 이용해서 DFS를 구현한다.
2. 반복문을 통해 방문하지 않았으면 DFS를 호출한다.
3. DFS에서 관련 노드들을 탐색해서 방문한다.
4. 한 번의 과정에서 count를 한 개씩 올린다.
💻결과 코드
public class Silver2_Q11724 {
static ArrayList<Integer>[] Node;
static boolean[] visited;
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
Node = new ArrayList[N+1];
visited = new boolean[N+1];
for (int i=1; i <= N; i++){
Node[i] = new ArrayList<>();
}
while (M > 0){
st = new StringTokenizer(br.readLine(), " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
Node[A].add(B);
Node[B].add(A);
M--;
}
for (int i = 1; i <= N; i++){
if (!visited[i]){
dfs(i);
count++;
}
}
System.out.println(count);
}
static void dfs(int N){
visited[N] = true;
for (int next : Node[N]){
if (!visited[next]){
visited[next] = true;
dfs(next);
}
}
}
}