반응형
24444번 너비 우선 탐색 1
https://www.acmicpc.net/problem/24444
24444번: 알고리즘 수업 - 너비 우선 탐색 1
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방
www.acmicpc.net
이번엔 BFS... DFS 보다 습득하는데 더 오래 걸린 듯 하다
그나마 이번 문제 풀면서 범위설정이나 조건이나 여러가지로 감을 좀 잡은듯
------
hint
해당 번호가 몇번째 순서로 도달했는지 저장하는 배열이 따로 필요
------
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static boolean[] isVisit; static ArrayList<Integer>[] a; 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()); int u, v; isVisit = new boolean[n+1]; a = new ArrayList[n+1]; for(int i = 1; i < n + 1; i++){ a[i] = new ArrayList<Integer>(); } for(int i = 0; i < m; i++){ st = new StringTokenizer(br.readLine()); u = Integer.parseInt(st.nextToken()); v = Integer.parseInt(st.nextToken()); a[u].add(v); a[v].add(u); } for(int i = 1; i < n + 1; i++){ if(!a[i].isEmpty()) { Collections.sort(a[i]); } } BFS(r, n, m); } static void BFS(int r, int n, int m){ // r이 1이라고 가정했을 때 Queue<Integer> queue = new LinkedList<>(); int temp; int[] count = new int[n+1]; int countNum = 1; isVisit[r] = true; count[r] = countNum++; queue.offer(r); while(!queue.isEmpty()){ temp = queue.poll(); for(int i = 0; i < a[temp].size(); i++) { if (!isVisit[a[temp].get(i)]) {//방문하지 않았을 때 실행 isVisit[a[temp].get(i)] = true; count[a[temp].get(i)] = countNum++; queue.offer(a[temp].get(i)); } } } for(int i = 1; i < n + 1; i++){ System.out.println(count[i]); } } } | cs |
실행시간 - 1996ms
너무 길어서 최적화좀 해주고싶은데.... BufferedReader말고는 상상이 안됨
반응형
'공부 > Algorithm' 카테고리의 다른 글
| 백준 13717 포켓몬Go 자바로 풀어 본 짧은 글 (0) | 2023.05.25 |
|---|---|
| 백준 1418 K-세준수 자바로 풀어 본 짧은 글 (0) | 2023.05.24 |
| 백준 13023번 ABCDE 자바로 풀어 본 짧은 글 (0) | 2023.04.22 |
| 백준 11004번 K번째 수 자바로 풀어 본 짧은 글 (0) | 2023.03.25 |
| 백준 2164번 카드2 자바로 풀어 본 짧은 글 (0) | 2023.03.18 |
