반응형

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

+ Recent posts

티스토리툴바