구름톤 챌린지 4주 차 학습 일기 (Day16 ~ 18)

🧩 문제 16. 연합

---

> 배운 점

• 그래프 탐색 ⇨ BFS

• 인접 행렬 활용

 

> 필요 변수 및 자료구조

- int[][] graph            ⇨ 인접 행렬

- boolean[] visited  / int[] visited   ⇨ 섬 방문 여부 확인 & 연합 여부 확인

- Queue<Integer>         ⇨ BFS 수행용

 

> 느낀 점

- 연합 개수 = BFS 수행 횟수

- 나는 boolean[] visited로 풀었는데,

int[] visited로 해서 while문 안에 현재 방문한 노드를 연합 번호에 할당하는 코드인 visited[now] = cnt; 를 넣어서 풀 수도 있다!

 

> 헷갈렸던 점

- while문 안에 들어가는 if문에서 간선의 존재 여부를 확인할 때,

   graph[now][next]와 graph[next][now]로 양방향 모두 확인해줘야한다..!!

 

 

> 정답 코드

import java.io.*;
import java.util.*;
 
class Main {
    static int N, M, cnt;    
    static int[][] graph;     // 인접 행렬
    static boolean[] visited; // 섬 방문 여부 확인 & 연합 여부 확인
    
    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());
        M = Integer.parseInt(st.nextToken());
        
        graph = new int[N + 1][N + 1];
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            graph[a][b] = 1; // 단방향
        }
        
        visited = new boolean[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            if(!visited[i]) {
                bfs(i);
                cnt++;
            }
        }
        
        System.out.println(cnt);
    }
    
    private static void bfs(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        
        visited[num] = true;
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(int next = 1 ; next <= N ; next++) {
                if(graph[now][next] == 1 && graph[next][now] == 1 && !visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                }
            }            
        }
    }
}

 

 

 

🧩 문제 17. 통신망 분석

---

> 배운 점

• 컴포넌트 : 그래프 내에서 서로 연결된 정점들의 집합

 

> 필요 변수 · 자료구조

• Com(List<Integer> list, double val)  ⇨ 객체 (찾아낸 컴포넌트 리스트, 밀도)

• List<Integer> result                            ⇨ 정답 저장 리스트

• Set<Integer> component                   ⇨ 도달한 컴퓨터들을 오름차순 집합으로 저장할 집합

 

> 느낀 점

•  클래스에 List도 인자로 가질 수 있다!

•  함수 리턴형을 객체로 받을 수도 있다!

•  필요한 변수/자료구조가 어떤 것이 있는지 초장에 고민을 진득하게 하는 시간이 필요한 것 같다.

 

 

> 헷갈렸던 점

•  도달한 컴퓨터들을 저장할 목록을 만들자

 

 

> 풀이

🔍 찾아야 할 것

1. 컴포넌트에 속한 컴퓨터 수

2. 컴포넌트에 속한 통신 회선 수

3. 컴포넌트에서 가장 작은 컴퓨터 번호

import java.util.*;
import java.io.*;
 
class Com {
    List<Integer> list; // 찾아낸 컴포넌트
    double val;         // 밀도
    
    public Com(List<Integer> list, double val) {
        this.list = list;
        this.val = val;
    }
}
 
public class Main {
    static int N, M;
 
    static List<Integer>[] A;
    static boolean[] visited;
    
    static List<Integer> result;    // 🔔 정답 저장 리스트
    static double density = 0;
    
    static StringBuilder sb = new StringBuilder();
    
    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());
        M = Integer.parseInt(st.nextToken());
        
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[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());
            
            A[a].add(b);
            A[b].add(a);
        }
        
        result = new ArrayList<>(); // 정답 저장 리스트
        
        for(int i = 1 ; i <= N ; i++) {
            if(!visited[i]) {
                Com com = bfs(i);
                
                List<Integer> tmp = com.list;
                double tmpDensity = com.val;
                
                if(Math.abs(tmpDensity - density) < 1e-8) { // [밀도가 같은 경우]
                    if(result.size() > tmp.size()) {        // 2번 조건) 현재 컴포넌트 배열이 더 크면, 컴퓨터 수가 가장 작은 컴포넌트 출력 (=result 값 확인)
                        result = tmp;
                        density = tmpDensity;
                    }
                    else if(result.size() == tmp.size()) {  // 3번 조건) 배열 크기가 같으면, 더 작은 컴퓨터 번호 갖는 컴포넌트 출력 (=첫 번째 값 비교)
                        if(tmp.get(0) < result.get(0)) {
                            result = tmp;
                            density = tmpDensity;
                        }
                    }
                }
                else if(tmpDensity > density) { // [밀도가 다른 경우, 가장 밀도가 높은 컴포넌트 출력]
                    result = tmp;
                    density = tmpDensity;
                }
            }
        }
        
        for(int r : result) {
            sb.append(r).append(" ");
        }
        System.out.println(sb);
    }
    
    private static Com bfs(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        
        Set<Integer> component = new TreeSet<>();   // 📍 도달한 컴퓨터들을 오름차순 집합으로 저장 (TreeSet : 객체 오름차순 정렬)
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            if(visited[now]) {
                continue;
            }
            
            visited[now] = true;
            component.add(now);
            
            for(int next : A[now]) {
                if(!visited[next]) {
                    queue.add(next);
                }
            }
        }
        
        /*** 🔔 내부 통선 회신 개수 확인 ***/
        int edge = 0;   // 간선 수 저장
        
        // 컴포넌트에 속한 모든 컴퓨터에 대해 순회
        for(int i : component) {
            for(int to : A[i]) {
                if(component.contains(to)) {    // contains 활용하기 위해 Set 쓰는 것!
                    edge++;
                }
            }
        }
        
        List<Integer> sortedList = new ArrayList<>(component);
        //Collections.sort(sortedList);
        
        return new Com(sortedList, (double) edge / component.size()); // "가장 밀도가 높은 컴포넌트" : 컴포넌트에 포함된 통신 회선 개수 / 컴퓨터 수
    }
}

 

 

🧩 문제 18. 중첩 점

---

> 배운 점

• DP - 3차원 매트릭스!

 

 

> 필요 변수 및 자료구조

• long[][][] dp = new int[2][][];        ⇨ 선 긋기를 중첩 기록해 모두 관리할 수 있는 DP 변수

  └ dp[0]  ⇨ 한 좌표에서 세로 선 개수만 기록

  └ dp[1]  ⇨ 한 좌표에서 가로 선 개수만  기록

 

• long spotCnt : 중첩 점 개수

 

• [선 개수, 방향]을 갖고 있는 데이터 (객체/배열)가 필요하다!

 

• D / U (상하) : 가로 선을 관리하는 dp[1]에서 추출하며, dp[1]의 값을 갱신한다.

• R / L (좌우)  : 세로 선을 관리하는 dp[0]에서 추출하며, dp[0]의 값을 갱신한다.

 

 

> 느낀 점

3차원 매트릭스 dp배열. 며칠 전에 문제로 풀 때 이 생각을 우째하지 싶었는데 이 문제에서 또 사용되었다

 

여기서 상하좌우 방향을 만날 때마다 각자의 조건문에 맞춰 반복문을 매번 수행하고,

중첩 점 개수를 갱신하고, dp를 갱신해주면 되는 것이었다..

 

정답 코드 보니 그리 어렵지 않음,,,,ㅠ