99클럽 코테 스터디 36일차 TIL , 전력망을 둘로 나누기

문제

풀이

입력으로 송전탑의 개수 n이 주어지고 송전탑끼리 연결되어 있는 정보가 담긴 리스트가 넘어온다.

하나의 선을 끊어서 두 개의 전력망을 만들어주는데 두 개의 차이가 가장 적은 경우를 return 해주면 된다.

 

제출 1 - 정답

import java.util.*;
class Solution {
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int[] wire : wires){	//map 만들어줌
            map.putIfAbsent(wire[0], new HashSet<>());
            map.putIfAbsent(wire[1], new HashSet<>());
            map.get(wire[0]).add(wire[1]);
            map.get(wire[1]).add(wire[0]);
        }

		//자르기
        for(int[] cut : wires){
            int i = cut[0];
            int j = cut[1];

            boolean flag = false;

            Set<Integer> left = new HashSet<>();
            left.add(i);
            Set<Integer> right = new HashSet<>();
            right.add(j);
            Deque<Integer> que = new ArrayDeque<>();

            for(int x : map.get(i)){
                if(x == j) continue;
                que.offer(x);
                left.add(x);
            }
            while(!que.isEmpty() && !flag){
                int x = que.poll();
                for(int y : map.get(x)){
                    if(y == j) {
                        flag = true;
                        break;
                    }
                    if(left.contains(y)) continue;
                    left.add(y);
                    que.offer(y);
                }
            }
            if(flag) continue;

            que.clear();

            for(int x : map.get(j)){
                if(x == i) continue;
                que.offer(x);
                right.add(x);
            }
            while(!que.isEmpty() && !flag){
                int x = que.poll();
                for(int y : map.get(x)){
                    if(y == i) {
                        flag = true;
                        break;
                    }
                    if(right.contains(y)) continue;
                    right.add(y);
                    que.offer(y);
                }
            }


            answer = Math.min(Math.abs(left.size() - right.size()), answer);
        }

        return answer;
    }
}

 

정답이긴 하지만 혹시 풀이를 보겠다면 밑에 것들을 보는 것을 추천한다.

쉽게 말하면  BFS를 요란하게 풀이한것이다.

제출 2 - 정답(bfs)

import java.util.*;
class Solution {
    public int solution(int n, int[][] wires) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=1;i<=n;i++){	
            map.put(i, new ArrayList<>());
        }
        for(int[] wire : wires){
            map.get(wire[0]).add(wire[1]);
            map.get(wire[1]).add(wire[0]);
        }

        int answer = Integer.MAX_VALUE;

        for(int[] wire : wires){
            int left = wire[0];
            int right = wire[1];
            int cnt = bfs(map, n, left, right);

            answer = Math.min(answer, Math.abs((n-cnt) - cnt));
        }

        return answer;
    }

    private int bfs(Map<Integer, List<Integer>> map, int n, int left, int right) {
        boolean[] visited = new boolean[n + 1];	//방문 체크
        Deque<Integer> que = new ArrayDeque<>();	
        //첫 값 설정
        visited[left] = true;	
        que.offer(left);
        int answer = 1;

        while (!que.isEmpty()) {
            int node = que.poll();

            for (int x : map.get(node)) {
                if(!visited[x] && x != right){	//방문 안했고 right 아니면
                    visited[x] = true;
                    que.offer(x);
                    answer++;
                }
            }
        }

        return answer;
    }

}

 

BFS를 깔끔하게 구현했다.

나누는 경우마다 BFS로 개수를 구해준 것

제출 3 - 정답(dfs)

import java.util.*;
class Solution {
    public int solution(int n, int[][] wires) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=1;i<=n;i++){
            map.put(i, new ArrayList<>());
        }
        for(int[] wire : wires){
            map.get(wire[0]).add(wire[1]);
            map.get(wire[1]).add(wire[0]);
        }

        int answer = Integer.MAX_VALUE;

        for(int[] wire : wires){
            int left = wire[0];
            int right = wire[1];
            int cnt = dfs(map, new boolean[n + 1], left, right);

            answer = Math.min(answer, Math.abs((n-cnt) - cnt));
        }

        return answer;
    }

    private int dfs(Map<Integer, List<Integer>> map, boolean[] visited, int left, int right) {
        visited[left] = true;
        int cnt = 1;

        for(int x : map.get(left)){
            if(!visited[x] && x != right){
                cnt += dfs(map, visited, x, right);
            }
        }

        return cnt;
    }
}

 

dfs풀이 bfs 풀이와 거의 유사하다.

속도는 dfs풀이가 가장 빨랐다.

TIL

• 너무너무 중요한 BFS, DFS