https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
//package Practice.P1260; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int N, M, V; static int[] ch; static Queue<Integer> Q = new LinkedList<>(); static ArrayList<Integer> adj[]; public static void main(String[] args) throws IOException { // System.setIn(new FileInputStream("src/Practice/P1260/input.txt")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); V = Integer.parseInt(st.nextToken()); ch = new int[N + 1]; adj = new ArrayList[N + 1]; for(int i = 0 ; i <= N; i++){ adj[i] = new ArrayList<>(); } for(int i = 0 ; i < M; i++){ st = new StringTokenizer(br.readLine()); int from = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); if(adj[from].size() == 0 && adj[to].size() == 0){ adj[from].add(to); adj[to].add(from); } int j; for(j = 0; j < adj[from].size(); j++){ if(to < adj[from].get(j)){ break; } } adj[from].add(j, to); for(j = 0; j < adj[to].size(); j++){ if(from < adj[to].get(j)){ break; } } adj[to].add(j, from); } ch[V] = 1; System.out.print(V + " "); dfs(V, 1); System.out.println(); // BFS int x; ch = new int[N + 1]; ch[V] = 1; Q.add(V); System.out.print(V + " "); while(!Q.isEmpty()){ x = Q.poll(); for(int i = 0; i < adj[x].size(); i++){ if(ch[adj[x].get(i)] == 0){ ch[adj[x].get(i)] = 1; System.out.print(adj[x].get(i) + " "); Q.add(adj[x].get(i)); } } } } static void dfs(int v, int n){ if(n == N){ return; }else{ for(int i = 0 ; i < adj[v].size(); i++){ if(ch[adj[v].get(i)] == 0){ System.out.print(adj[v].get(i) + " "); ch[adj[v].get(i)] = 1; dfs(adj[v].get(i), n + 1); } } } } }
dfs를 먼저, 그리고 bfs를 그 후에 탐색하면서 print로 찍어내는 것이 문제였습니다.
간선 정보는 arraylist의 배열을 만들어서 인접리스트에 담았습니다.
dfs는 따로 함수를 만들어주었고 bfs는 main에서 큐로 구현했습니다.
우선 문제의 다음 조건이 핵심입니다.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
위 조건을 만족시키면서 탐색하기 위해서는 두 가지 방법이 존재할 것입니다.
1. 간선 정보를 인접리스트에 담을 때 정렬해서 담는다.
2. 아무렇게나 간선 정보를 담은 후, 탐색할 때 오름차순으로 탐색한다.
저는 1번 방법으로 접근했습니다.
그 이유는 탐색을 두 번 하기 때문에 이중으로 시간복잡도가 증가할 것이라 생각했기 때문입니다.
탐색하기 전에 정렬을 해놓는 1번 방법을 쓴다면,
탐색을 1000번 할 때도 한 번의 정렬만으로 가능하겠죠?
for(int i = 0 ; i < M; i++){ st = new StringTokenizer(br.readLine()); int from = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); if(adj[from].size() == 0 && adj[to].size() == 0){ adj[from].add(to); adj[to].add(from); } int j; for(j = 0; j < adj[from].size(); j++){ if(to < adj[from].get(j)){ break; } } adj[from].add(j, to); for(j = 0; j < adj[to].size(); j++){ if(from < adj[to].get(j)){ break; } } adj[to].add(j, from); }
adj 인접리스트에 간선이 들어가있지 않아서 size가 0일 때를 따로 빼주어서
간선이 우선 들어가도록 해주어야 합니다. 그 후에 대소비교를 하면서 간선을 넣는 것이죠.
따로 size가 0일 때를 빼주지 않는다면,
adj[from].size() 와 adj[to].size() 는 0을 유지하기 때문에
대소비교하면서 간선을 넣는 반복문이 돌아가지를 않습니다.
그리고나서 size가 1 이상일 때는 기존 간선의 정점 번호와 대소비교를 해서
정점 번호가 오름차순이 되도록 add를 해줍니다.
-> add(인덱스, 넣을 값) 을 해주면 인덱스에 값이 들어가면서 뒤로 자동으로 밀려납니다.
양방향 간선이기에 from과 to 동일하게 작업해줍니다.
dfs에서는 현재까지 탐색한 정점의 개수를 담는 n을 1증가시키면서 매개변수로 넘겨줍니다.
그리고 n이 정점의 총 개수가 되면 return 시키면서 탐색을 종료합니다.
방문여부를 저장하는 ch 배열은 탐색 후 0으로 풀어주지 않습니다!!!!!!!!!!
그래야 문제의 조건을 만족하면서, 한 번의 완전탐색을 한 후에 종료합니다.
만약 ch배열을 0으로 풀어줘서 dfs를 반복시킨다면 완전 탐색이 여러번 반복됩니다.
'Algorithm > 백준' 카테고리의 다른 글
[백준][11437번 : LCA] 최소 공통 조상 문제 (0) | 2023.04.21 |
---|---|
[백준][Java] 14503번 로봇 청소기 풀이 (구현, 시뮬레이션) (2) | 2023.04.18 |
[백준][c/c++] 2231번: 분해합 (0) | 2022.02.20 |
[백준][C/C++] 9020번: 골드바흐의 추측 (0) | 2022.02.18 |
[백준][C++] 10870 피보나치 수 5 (0) | 2022.01.31 |