구름톤 챌린지: 4주차(230904~230905)

230904

Day16 문제풀이

코드

import java.io.*;
import java.util.*;

class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int N;
    static int count = 0;
    static int[] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(tk.nextToken());
        int M = Integer.parseInt(tk.nextToken());

        for(int i=0; i<N; i++) graph.add(new ArrayList<Integer>());
        visited = new int[N];

        for(int i=0; i<M; i++) {
            tk = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(tk.nextToken()) - 1;
            int v = Integer.parseInt(tk.nextToken()) - 1;

            graph.get(u).add(v);
        }

        for(int i=0; i<N; i++) bfs(i);

        System.out.print(count);
    }

    public static void bfs(int R) {
        if(visited[R] == 0) visited[R] = ++count;
        else return;

        Queue<Integer> queue = new LinkedList();
        queue.offer(R);

        while(!queue.isEmpty()) {
            int u = queue.poll();

            for(int v : graph.get(u)) {
                if(visited[v] == 0 && graph.get(v).contains(u)) {
                    visited[v] = visited[R];
                    queue.offer(v);
                }
            }
        }
    }
}

중요

• 해당 문제에서는 단방향이 아닌 양방향일 경우에만 연합으로 치기 때문에 기존의 bfs에서 방문 여부 외에도 graph.get(v).contains(u)로 양방향 조건을 추가해주어야 한다.
• bfs에서 queue에 v를 offer하는 걸 잊지 말자. v를 offer하지 않으면 다음 이웃 노드로 넘어갈 수 없다

230905

Day17 문제풀이

코드

import java.io.*;
import java.util.*;
class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> component = new ArrayList<>();
    static HashMap<ArrayList<Integer>, Integer> map = new HashMap<>();

    static int N;
    static int[] visited;
    static int count = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(tk.nextToken());
        int M = Integer.parseInt(tk.nextToken());

        int[] countU = new int[N];
        visited = new int[N];

        for(int i=0; i<N; i++) graph.add(new ArrayList<Integer>());

        for(int i=0; i<M; i++) {
            tk = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(tk.nextToken()) - 1;
            int v = Integer.parseInt(tk.nextToken()) - 1;

            countU[u]++;

            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        for(int i=0; i<N; i++) bfs(i);

        // 밀도가 높은 컴포넌트
        Collections.sort(component, (o1, o2) -> {
            // 컴퓨터의 수가 가장 작은 컴포넌트
            if(map.get(o1) == map.get(o2)) {
                // 더 작은 번호 컴퓨터 컴포넌트
                if(o1.size() == o2.size()) {
                    return Collections.min(o1) - Collections.min(o2);
                } else {
                    return o1.size() - o2.size();
                }
            } else {
                return map.get(o2) - map.get(o1);
            }
        });

        Collections.sort(component.get(0));
        for(int i : component.get(0)) System.out.print((i+1) + " ");
    }

    public static void bfs(int R) {
        if(graph.get(R).size() == 0 || visited[R] != 0) return;

        visited[R] = ++count;
        int countComponentTemp = 0; // 통신 회선 개수 카운트
        component.add(new ArrayList<Integer>());
        component.get(component.size()-1).add(R);

        Queue<Integer> queue = new LinkedList();
        queue.offer(R);

        while(!queue.isEmpty()) {
            int u = queue.poll();

            for(int v : graph.get(u)) {
                countComponentTemp++;
                if(visited[v] == 0) {
                    visited[v] = visited[R];
                    component.get(component.size()-1).add(v);
                    queue.offer(v);
                }
            }
        }

        map.put(component.get(component.size()-1), countComponentTemp / 2);
    }
}

중요

• HashMap에서 키 값을 단일값만 줄 수 있다고 생각했는데, 배열 전체도 키 값으로 줄 수 있다는 것을 알게 되었다.
  (1 뿐만 아니라 {1,3,6} 도 key로 사용할 수 있다는 의미)