DFS 기본 로직
key) 후입선출, 스택 자료구조 사용, 재귀 형태
1. 시작 노드를 정한 후 사용할 자료구조 초기화
> 필요한 초기 작업은 무엇인가? 인접 리스트로 그래프 표현하기, 방문 배열 (visited) 초기화하기
스택에 노드를 삽입할 때 visited T로 바꿔주는 것!
2. 스택에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 다시 스택에 삽입
이미 다녀간 노드는 재삽입하지 않는 것이 원칙임.
> 모든 노드를 다 돌 때까지 반복함.
백준 11724 연결 요소의 개수
https://www.acmicpc.net/problem/11724
11724번: 연결 요소의 개수
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어
www.acmicpc.net
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] arr;
static boolean visited[];
static void DFS(int s) {
if(visited[s]) {
return; //리턴 조건.
}
visited[s]=true; //방문했으니 true로 바꿔주기.
for(int a: arr[s]) {
if(visited[a]==false)
DFS(a);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //정점
int M = Integer.parseInt(st.nextToken()); //간선
arr = new ArrayList[N+1];
visited = new boolean[N+1];
for(int i = 1; i < N+1; i++) {
arr[i] = new ArrayList<Integer>(); //인접 리스트 초기화
}
for(int i = 0; i < M; i++) { //엣지 개수만큼 반복.
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
//연결 요소의 개수는 그래프가 총 몇 덩어리(?)인지
arr[v].add(u);
arr[u].add(v);
}
int count = 0; //연결 요소 갯수
for(int i =1; i < N+1; i++) { //노드갯수만큼 반복
if(!visited[i]) { //방문하지 않은 노드라면
count++;
DFS(i); // i를 시작노드로 DFS 실행
}
}
System.out.println(count);
}
}
백준 2023 신기한 소수
https://www.acmicpc.net/problem/2023
2023번: 신기한 소수
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수
www.acmicpc.net
import java.io.*;
import java.util.*;
public class Main {
static int n;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// StringBuilder sb = new StringBuilder();
// StringTokenizer st;
n = Integer.parseInt(br.readLine());
DFS(2, 1);
DFS(3, 1);
DFS(5, 1);
DFS(7, 1);
}
static boolean isPrimeNum(int num) {
for(int i = 2; i<= num/2; i++) {
if(num % i == 0)
return false;
}
return true;
}
static void DFS(int num, int j) { //j:자릿수
if( j == n) {
if (isPrimeNum(num)) {
System.out.println(num);
}
return;
}
for(int i = 1; i <= 9; i++) {
if( i % 2 == 0)
continue; //짝수는 탐색 X
if(isPrimeNum(num*10 + i)) {
DFS(num*10+i, j+1);
}
}
}
}
백준 1260 BFS와 DFS
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer> A []; //인접리스트
static boolean visited[];
static int n, m, v;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); //노드 개수
m = Integer.parseInt(st.nextToken()); //에지 개수
v = Integer.parseInt(st.nextToken()); //시작점
A = new ArrayList[n+1];
for(int i = 1; i < n+1; i++) {
A[i] = new ArrayList<Integer>(); //인접 리스트 초기화
}
for(int i = 1; i < m+1; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
A[s].add(e);
A[e].add(s); //인접 그래프 추가
}
for(int i = 1; i < n+1; i++) {
Collections.sort(A[i]);
} //번호가 작은 것들을 먼저 방문하기 위함.
visited = new boolean[n+1];
DFS(v);
System.out.println();
visited = new boolean[n+1];
BFS(v);
}
static void DFS(int s) { //시작 노드 v
System.out.printf(s + " ");
if(visited[s]) return;
visited[s] = true;
for(int a : A[s]) {
if(!visited[a])
DFS(a);
}
}
static void BFS(int s) {
Queue<Integer> q = new LinkedList<Integer>();
q.add(s);
visited[s] = true;
while(!q.isEmpty()) {
int current_node = q.poll();
System.out.printf(current_node + " ");
for(int a: A[current_node]) {
if(!visited[a]) {
visited[a] = true;
q.add(a);
}
}
}
}
}
'Algorithms > study log' 카테고리의 다른 글
[java] 다익스트라 알고리즘 (0) | 2024.02.01 |
---|---|
[백준 나무자르기] 이분탐색시 시작 혹은 끝 지점 설정하는 방법 (0) | 2024.01.17 |
[java] 이분탐색 (2) | 2024.01.12 |
[Algorithm] Greedy 그리디 알고리즘 (1) | 2023.12.27 |
[JAVA] 시뮬레이션,구현 (0) | 2023.12.01 |