구름톤 챌린지 3주 차 학습 일기 (Day14 ~ 15)

🧩 문제 14. 작은 노드

---

우와 바지 입었다!!!

> 배운 점

• 그래프 탐색

• 인접 리스트 vs 인접 행렬

 

◻ 인접 리스트

👍 공간 복잡도 면에서 효율적 (실제 연결된 정점의 정보만 저장하므로)

👎 두 정점을 연결하는 간선이 존재하는지 빠르게 확인은 불가능

 

◻ 인접 행렬

👍 어떤 정점끼리 연결되어있는지 빠르게 확인 가능 (시간 복잡도 : O(1))

👎

  - 공간 복잡도가 너무 큼 (∵ 주어지는 정점 개수의 제곱에 비례하는 크기의 배열을 선언해야 하므로)

  - 인접 정점의 정보를 알기 위해 O(N)의 시간을 투자해야 함

 

 

> 느낀 점

DFS나 BFS 활용하면 쉽게 풀리겠지 하고 만만하게(?) 보고 BFS로 풀었는데

BFS문의 반복문 안에 break를 넣지 않아서 자꾸 틀렸었고 이것 떄문에 시간을 많이 잡아먹었다ㅠㅠ

 

 

> 헷갈렸던 점

🔔 BFS문의 반복문 안에 break를 넣어야 하는 이유

 : 방문할 수 있는 정점이 나오면, 반복문 탈출해야 하므로

    ▷ break문이 없다면 now와 인접한 모든 노드를 방문하게 되며, 번호가 가장 작은 노드부터 이동하지 않을 수 있다.

        그렇기 때문에 가장 작은 번호 노드로만 이동하며, 인접한 모든 노드를 방문하지 않기 위해 사용한다.

 

import java.io.*;
import java.util.*;
 
class Main {
    static int N, M, K;
 
    static ArrayList<Integer>[] list;    // 인접 리스트
    static boolean[] visited;
    
    static int cnt, ans;    // 방문한 서로 다른 노드 개수, 마지막 노드 번호
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());    // 노드 개수 (1 ~ N)
        M = Integer.parseInt(st.nextToken());    // 간선 개수 (양방향)
        K = Integer.parseInt(st.nextToken());    // 시작 노드 번호
        
        // 변수들 초기화
        list = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            list[i] = new ArrayList<>();
        }
        
        visited = new boolean[N + 1];
 
        // 입력 받기
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            // 양방향
            list[a].add(b);
            list[b].add(a);
        }
        
        // 번호가 가장 작은 노드 순으로 이동하도록 오름차순 정렬
        for(int i = 1 ; i <= N ; i++) {
            Collections.sort(list[i]);
        }
        
        bfs(K);
        System.out.println(cnt + " " + ans);
    }
    
    private static void bfs(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        
        visited[num] = true;
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            ans = now;
            cnt++;
            
            for(int next : list[now]) { // 다음 인접 정점으로 이동
                if(!visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                    break;    // 🔔 가장 작은 번호 노드로만 이동하게 하고, 이후 노드는 못 가게 종료시킴
                }
            }
        }
    }
}

 

 

 

 

🧩 문제 15. 과일 구매

---

오 돋보기까지....

> 배운 점

• 배낭(Knapsack) 문제 + 그리디

• 사용자 정의 정렬 방법

 

 

> 느낀 점

: 하 그리디 문제를 많이 풀어봐야겠다고 느꼈다!

 

그리고 구름... 정해 코드를 보면 좀 어려운 버전으로 올려주시는 것 같다.

다른 분들 정답 코드도 있나 참고해보려고 검색해봤는데 훨씬 더 이해하기 쉬웠던...

 

그리고 배낭 문제도 미루다가 안 풀고 있었는데 풀어봐야겠다!

 

> 헷갈렸던 점

: 정렬 조건 설정

// 정렬 조건 설정
Collections.sort(cost, (a, b) -> Double.compare(b[0], a[0]) != 0 ? Double.compare(b[0], a[0]) : Double.compare(b[1], a[1]));