๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1260
- ๊ทธ๋ํ๋ฅผ DFS๋ก ํ์ํ ๊ฒฐ๊ณผ์ BFS๋ก ํ์ํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ๋จ, ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ ์ด ์ฌ๋ฌ ๊ฐ์ธ ๊ฒฝ์ฐ์๋ ์ ์ ๋ฒํธ๊ฐ ์์ ๊ฒ์ ๋จผ์ ๋ฐฉ๋ฌธํ๊ณ , ๋ ์ด์ ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ด ์๋ ๊ฒฝ์ฐ ์ข ๋ฃํ๋ค. ์ ์ ๋ฒํธ๋ 1๋ฒ๋ถํฐ N๋ฒ๊น์ง์ด๋ค.
- ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N(1 ≤ N ≤ 1,000), ๊ฐ์ ์ ๊ฐ์ M(1 ≤ M ≤ 10,000), ํ์์ ์์ํ ์ ์ ์ ๋ฒํธ V๊ฐ ์ฃผ์ด์ง๋ค.
- ๋ค์ M๊ฐ์ ์ค์๋ ๊ฐ์ ์ด ์ฐ๊ฒฐํ๋ ๋ ์ ์ ์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค.
- ์ด๋ค ๋ ์ ์ ์ฌ์ด์ ์ฌ๋ฌ ๊ฐ์ ๊ฐ์ ์ด ์์ ์ ์๋ค.
- ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๊ฐ์ ์ ์๋ฐฉํฅ์ด๋ค.
- ์ฒซ์งธ ์ค์ DFS๋ฅผ ์ํํ ๊ฒฐ๊ณผ๋ฅผ, ๊ทธ ๋ค์ ์ค์๋ BFS๋ฅผ ์ํํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ค. V๋ถํฐ ๋ฐฉ๋ฌธ๋ ์ ์ ์์๋๋ก ์ถ๋ ฅํ๋ฉด ๋๋ค.
์์ด๋์ด
- ์ฐ์ ์ฐ๊ฒฐ ๋ ธ๋๋ฅผ ์๋ก ๊ธฐ๋กํ๊ธฐ ์ํด TreeSet ๋ฐฐ์ด์ N + 1ํฌ๊ธฐ๋ก ์ ์ธํ๋ค.
- TreeSet์ผ๋ก ๋ฐฐ์ด์ ์ ์ธํ ์ด์ ๋ ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ ์ด ์ฌ๋ฌ๊ฐ์ผ๋, ์ ์ ๋ฒํธ๊ฐ ์์ ๊ฒ์ ๋จผ์ ๋ฐฉ๋ฌธํ๋ค๊ณ ํ์์ผ๋ฏ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌ์ ํ๊ธฐ์ํด TreeSet์ ์ผ๋ค.
- ๊ทธ๋ฆฌ๊ณ DFS์ BFS์ ๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํ๊ธฐ ์ํด ArrayList๋ฅผ ์ ์ธํ๊ณ , ๊ฐ ๋ ธ๋์ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ์ํด N + 1 ํฌ๊ธฐ์ boolean ๋ฐฐ์ด์ ์ ์ธํ๋ค.
- ๋จผ์ DFS๋ฅผ ์์ ์ ์ ์ธ V๋ถํฐ ๋๋ฆฌ๊ธฐ์ , ๊ฒฐ๊ณผ๊ฐ ArrayList์ ์ ์ฅํ๊ณ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ํด์ค๋ค.
- ๊ทธ๋ฆฌ๊ณ DFS๋ฅผ V๋ถํฐ ๋๋ฆฌ๋ฉด์ ๊ธฐ์กด ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ ธ๋๋ฒํธ์ค์ ๋ง์ฝ ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋๊ฐ ์๋ค๋ฉด ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ํด์ฃผ๊ณ ๊ฒฐ๊ณผ๊ฐ ArrayList์ ์ ์ฅํด์ค๋ค.
- ๊ทธ๋ฆฌ๊ณ ํด๋น ๋ ธ๋ ๋ฒํธ๋ก ๋ค์ DFS๋ฅผ ๋๋ฆฐ๋ค. (DFS๋ ๊น์ด ์ฐ์ ํ์ ์๊ณ ๋ฆฌ์ฆ์ด๊ธฐ ๋๋ฌธ)
- DFS๋ฅผ ๋๋ฆฌ๋ค๊ฐ ๊ฒฐ๊ณผ๊ฐ ArrayList์ ํฌ๊ธฐ๊ฐ ๋ ธ๋ ๊ฐ์์ ๊ฐ๋ค๋ฉด DFS๋ฅผ ์ข ๋ฃํ๋ค.
- DFS๋ฅผ ์ข ๋ฃํ๊ณ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ์ ์ฅํ๋ boolean ๋ฐฐ์ด์ ์ด๊ธฐํ ์์ผ์ค ๋ค, BFS๋ฅผ ๋๋ฆฐ๋ค.
- ๋ง์ฐฌ๊ฐ์ง๋ก BFS๋ ์์ ๋ ธ๋ V๋ถํฐ ์์ํ๊ณ ์ด๊ธฐ ๋ ธ๋๊ฐ์ BFS ๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํ๋ ArrayList์ ์ ์ฅํ๊ณ ํด๋น ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ํด์ค๋ค, Queue์ ๋ฃ๋๋ค.
- ๊ทธ๋ฆฌ๊ณ Queue๊ฐ ๋น๋๊น์ง while๋ฌธ์ ๋๋ฆฌ๋๋ฐ, while๋ฌธ ์์์ Queue์ ๋ค์ด์๋ ๊ฐ์ ๋นผ์ ์๋ก์ด ๋ณ์์ ์ ์ฅํ๊ณ ๊ทธ ๋ณ์๋ฅผ ๊ธฐ์ค์ผ๋ก for๋ฌธ์ ํตํด ์ฐ๊ฒฐ๋์ด ์๋ ๋ ธ๋์ค์ ๋ฐฉ๋ฌธํ์ง ์์ ๊ฒ์ด ์๋ค๋ฉด ํด๋น ๋ ธ๋๋ฅผ Queue์ ๋ฃ์ด๋๊ณ , ๋ฐฉ๋ฌธ์ฒ์น๋ฅผ ํด์ค ๋ค, ๊ฒฐ๊ณผ๊ฐ ArrayList์ ์ ์ฅํ๋ค.
- for๋ฌธ์ผ๋ก ๊ธฐ์กด ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด์๋ ๋ ธ๋๋ค์ ๋ชจ๋ ๋ฐฉ๋ฌธํ๋ค๋ฉด ์๋กญ๊ฒ Queue์ ๋ฃ์ด์ง ๋ ธ๋ ๊ฐ๋ค์ ๊ธฐ์ค์ผ๋ก ๋ค์ for๋ฌธ์ ๋๋ฆฐ๋ค.
- ์ต์ข ์ ์ผ๋ก ๋ชจ๋ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ค๋ฉด ๋ ์ด์ Queue์ ๋จ์์๋ ๋ ธ๋๊ฐ ์๊ธฐ ๋๋ฌธ์ while๋ฌธ์ด ์ข ๋ฃ๋๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- ์ฌ์ค BFS๋ ๊ทธ๋๋ง ์ฝ๊ฒ ํ์๋ ๊ฒ ๊ฐ์๋ฐ... DFS๊ฐ ๋๋ฌด ์ค๋๋ง์ด๋ค ๋ณด๋ ๋ฐฉ๋ฒ์ด ์๊ฐ์ด ์๋์ ์กฐ๊ธ ์ค๋ ๊ณ ๋ฏผํ๋ ๊ฒ ๊ฐ๋ค.
- ๊ทธ๋ฆฌ๊ณ ๊ณ์ DFS ๊ฒฐ๊ณผ๊ฐ ๋์ค๋๊ฒ ์ด์ํด์ ๋ญ๊ฐ ๋ฌธ์ ์ธ์ง ๋ณด๋๊น ๊ฒฐ๊ณผ๊ฐ ์ ์ฅ์ DFS๋ฅผ ๋๋ฆฌ๊ณ ๋์ ํ๊ณ ์๋ ๊ฒ์ด์๋ค...ใ ใ ใ ......์ฌ์ํ ๊ฒ์ด๊ธด ํ์ง๋ง... ๊ทธ๋๋ ์ฃผ์ํด์ ํ์ด์ผ๊ฒ ๋ค...
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ1260 {
static TreeSet<Integer>[] arr;
static ArrayList<Integer> d_result;
static ArrayList<Integer> b_result;
static boolean visited[];
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 = new StringTokenizer(br.readLine());
// ์ ์ ์ ๊ฐ์
N = Integer.parseInt(st.nextToken());
// ๊ฐ์ ์ ๊ฐ์
int M = Integer.parseInt(st.nextToken());
// ์์ํ ์ ์ ์ ๋ฒํธ
int V = Integer.parseInt(st.nextToken());
// ์ฐ๊ฒฐ ์ ๋ณด๋ฅผ ์ ์ฅํ ArrayList ๋ฐฐ์ด
arr = new TreeSet[N + 1];
// dfs ๊ฒฐ๊ณผ๊ฐ ์ ์ฅํ ArrayList
d_result = new ArrayList<>();
// bfs ๊ฒฐ๊ณผ๊ฐ ์ ์ฅํ ArrayList
b_result = new ArrayList<>();
// ๋
ธ๋์ ๋ฐฉ๋ฌธ์ฌ๋ถ๋ฅผ ์ ์ฅํ ๋ฐฐ์ด
visited = new boolean[N + 1];
for(int i = 1; i <= N; i++){
// ๋ฐฐ์ด ์์๋ฅผ TreeSet์ผ๋ก ์ด๊ธฐํ
arr[i] = new TreeSet<Integer>();
}
for(int i = 0; i < M; i++){
StringTokenizer st2 = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st2.nextToken());
int n2 = Integer.parseInt(st2.nextToken());
// ๊ฐ ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ถ๊ฐ
arr[n1].add(n2);
arr[n2].add(n1);
}
// DFS์ ๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํ ArrayList์ ์ด๊ธฐ ๋
ธ๋๊ฐ์ ์ ์ฅ
d_result.add(V);
// ์ด๊ธฐ ๋
ธ๋์ ๋ฐฉ๋ฌธ๊ฐ์ true๋ก ๋ณํ
visited[V] = true;
// DFS๋ฅผ ๋๋ฆผ
DFS(V);
// BFs๋ฅผ ๋๋ฆฌ๊ธฐ์ ๋ฐฉ๋ฌธ์ฌ๋ถ๋ฅผ ์ด๊ธฐํ
visited = new boolean[N + 1];
// BFS๋ฅผ ๋๋ฆผ
BFS(V);
// DFS ๊ฒฐ๊ณผ๊ฐ ์ถ๋ ฅ
for(int i = 0; i < d_result.size(); i++){
sb.append(d_result.get(i) + " ");
}
sb.append("\n");
// BFS ๊ฒฐ๊ณผ๊ฐ ์ถ๋ ฅ
for(int i = 0; i < b_result.size(); i++){
sb.append(b_result.get(i) + " ");
}
System.out.println(sb);
}
static public void DFS(int a){
// ๋ง์ฝ DFS์ ๊ฒฐ๊ณผ๊ฐ ArrayList์ ํฌ๊ธฐ๊ฐ ๋
ธ๋ ๊ฐ์์ ๊ฐ๋ค๋ฉด
if(d_result.size() == N){
return;
}
// ๊ธฐ์กด ๋
ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋
ธ๋์ค
for(int i : arr[a]){
// ๋ง์ฝ ํด๋น ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉด
if(!visited[i]){
// ํด๋น ๋
ธ๋์ ๊ฒฐ๊ณผ๊ฐ์ true๋ก ๋ฐ๊พธ๊ณ
visited[i] = true;
// ๊ทธ๋ฆฌ๊ณ DFS ๊ฒฐ๊ณผ๊ฐ ArrayList์ ํด๋น ๋
ธ๋๋ฅผ ๋ฃ์
d_result.add(i);
// ํด๋น ๋
ธ๋๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ค์ DFS๋ฅผ ๋๋ฆผ
DFS(i);
}
}
}
static public void BFS(int a){
Queue<Integer> q = new LinkedList<>();
// ์ด๊ธฐ ๋
ธ๋๊ฐ์ Queue์ ๋ฃ๊ณ
q.offer(a);
// bfs ๊ฒฐ๊ณผ๊ฐ ArrayList์ ํด๋น ๋
ธ๋๊ฐ ์ ์ฅ
b_result.add(a);
// ๊ทธ๋ฆฌ๊ณ ํด๋น ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ
visited[a] = true;
while(!q.isEmpty()){
int node = q.poll();
// ํด๋น ๋
ธ๋์ ์๋ ๊ฐ๋ค ์ค
for(int i: arr[node]){
// ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋๊ฐ ์๋ค๋ฉด
if(!visited[i]){
// ํด๋น ๋
ธ๋ ๋ฒํธ๋ฅผ Queue์ ๋ฃ์ด์ฃผ๊ณ
q.offer(i);
// ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ํด์ค
visited[i] = true;
// ๊ทธ๋ฆฌ๊ณ bfs ๊ฒฐ๊ณผ๊ฐ ArrayList์ ํด๋น ๋
ธ๋ ์ ์ฅ
b_result.add(i);
}
}
}
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 1541 ์์ด๋ฒ๋ฆฐ ๊ดํธ (0) | 2024.08.02 |
---|---|
[Java] BOJ 1927 ์ต์ ํ (0) | 2024.08.01 |
[Java] BOJ 1012 ์ ๊ธฐ๋ ๋ฐฐ์ถ (0) | 2024.07.31 |
[Java] BOJ 7626 Four Squares (2) | 2024.07.31 |
[Java] BOJ 11727 2รn ํ์ผ๋ง 2 (0) | 2024.07.30 |