Today I Learned

오늘은 내일 코테를 대비해 좀 부족하다 싶었던 dfs문제를 풀어봤다.

전력망 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

문제

n개의 송전탑이 트리 형태로 모두 연결되어있다. 전선 하나를 끊어서 2개의 그룹으로 나누려고 한다. n-1개의 전선 정보가 2차원 배열 wires로 주어진다. 임의의 전선을 잘랐을 때, 두 그룹의 개수 차이가 가장 적을때의 그 절대값을 반환해라.

풀이 과정

1. 우선 wires 배열을 기반으로 이차원 리스트를 만들어 양방향 그래프를 구현한다. 주의할 점은 1~n까지의 숫자 노드를 사용하니 인덱스를 맞춰줘야한다.

2. dfs 메서드를 만든다. 방문여부를 체크하고 count를 하나 올리고 인접 그래프에서 재귀로 탐색한다.

3. for문으로 전선을 하나씩 끊어서 재귀를 돌려본다. 전선 정보를 하나씩 없에고 탐색한뒤 다시 없엔 정보를 추가해 for문을 이어나가는 방식이다.

4. 방문 여부와 count는 바깥 for문이 증가할때마다 초기화 시켜준다. 안쪽 for문에서 방문 하지 않았으면 dfs를 돌려 count 수를 체크하는 방식이다. 전선 하나만 끊으면 딱 2그룹만 생기므로 count를 리스트에 저장해 0번째랑 1번째 카운트의 차이를 절대값으로 감싼다. 이 숫자를 answer와 비교해 작은 값만 answer에 남긴다.

5. 위의 과정을 진행하면 최소 차이만 answer에 남게된다.

Trouble

• ArrayList의 remove 메서드를 사용할 때 조심해야 한다.
  E remove(int index) : 리스트의 index에 해당하는 요소를 제거한다.
  boolean remove(Object o) : 리스트 안에 o가 있으면 o를 제거한다.

• 이 문제에서는 List\ 를 사용했기 때문에 의도한 방식으로 사용하기 위해서는 remove(Integer o) 값을 사용해야 제대로 제거할 수 있다.
  그냥 int 값을 넣으면 인덱스 값이 지워지므로 제대로 지워지지 않는다.

Java 코드

import java.util.*;
class Solution {
    List<List<Integer>> graph;
    boolean[] visited;
    int count;
    
    public void dfs(int x){
        visited[x] = true;
        count++;
        
        for(int y : graph.get(x)){
            if(!visited[y]) dfs(y);
        }
    }
    
    public int solution(int n, int[][] wires) {
        int answer = 100;
        int len = wires.length;
        
        graph = new ArrayList<>();
        visited = new boolean[n+1];
        
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        
        for(int i=0; i<len; i++){
            graph.get(wires[i][0]).add(wires[i][1]);
            graph.get(wires[i][1]).add(wires[i][0]);
        }
        
        for(int i=0; i<len; i++){
            Integer s = wires[i][0];
            Integer e = wires[i][1];
            
            graph.get(s).remove(e);
            graph.get(e).remove(s);
            
            Arrays.fill(visited, false);
            List<Integer> cList = new ArrayList<>();
            
            for(int j=1; j<=n; j++){
                if(!visited[j]){
                    count = 0;
                    dfs(j);
                    cList.add(count);
                }
            }
            
            int a = Math.abs(cList.get(0) - cList.get(1));
            answer = Math.min(answer,a);
            
            graph.get(s).add(e);
            graph.get(e).add(s);
        }
        return answer;
    }
}