[Java] Stack를 활용한 DFS 알고리즘으로 푼 문제

DFS 알고리즘에는 꼭 재귀 메서드를 호출하는게 아닌 Stack이나 Queue를 활용하는 방법도 있다고 한다.

 

해당 방식으로 풀게된 문제는 프로그래머스의 전력망을 둘로 나누기이다.

---

문제 설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있고 여기서 하나의 전선을 끊어서 현재의 전력망 네트워크를 2개로 분할하는 문제이다.

단! 두 전력망이 가지게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 한다.

---

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• • wires는 길이가 n-1인 정수형 2차원 배열입니다.
    • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
    • 1 ≤ v1 < v2 ≤ n 입니다.
    • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

---

입출력 예

n	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1
14	[[1, 6], [1, 3], [1, 4], [2, 4], [4, 9], [5, 6], [6, 8], [6, 7], [6, 13], [6, 14], [9, 10], [10, 11], [11, 12]]	2

 

---

주어진 wires를 살펴보면 단방향의 데이터만 주어져 있다. 이를 양방향에 맞게 조절해서 이렇게도 갈수 있고 저렇게도 갈수 있게 만들어야 한다. 그리고 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않기에 가능한 문제로 보인다.

프로그램의 흐름은 아래와 같다.

1. 전력망 연결작업(가는 길 , 오는 길 구축)
2. wires 반복문 시작
   1. 만들어진 map에 해당 전력망 짜르기
   2. dfs 메서드 호출
      1. 잘라진 전력망에서 시작값을 stack에 담기
      2. stack.isEmpty()를 통해 반복문 돌아서 연결된 곳 구석구석까지 돌기
      3. count 증가
      4. count 반환
   3. 최저값 비교
   4. 만들어진 map에 해당 전력망 복구

입출력 예#1

 

 

그림대로 진행하게 되면 정답을 구할수 있게 된다.

---

코드

import java.util.*;
class Solution {
    Map<Integer , List<Integer>> map = new HashMap<>();
    int answer = 0;
    
    public int solution(int n, int[][] wires) {
        answer = n;
        // 전력망 연결하기
        for (int i = 0; i < wires.length; i++) {
            int target = wires[i][0];
            int connect = wires[i][1];
            input(target , connect);
            input(connect , target);
        }
        // 주어진 wires 배열을 반복문으로 돌면서 하나씩 끊어보기
        for (int i = 0; i < wires.length; i++) {
            int start = wires[i][0];
            int end = wires[i][1];
            
            // 자르기
            List<Integer> startCutList = map.get(start);
            startCutList.removeIf(x -> x == end);
            map.put(start , startCutList);
            
            List<Integer> endCutList = map.get(end);
            endCutList.removeIf(x -> x == start);
            map.put(end , endCutList);
            
            // 시작값의 dfs() 호출
            int startCnt = dfs(start , n);
            // 종료값의 dfs() 호출
            int endCnt = dfs(end , n);
            
            // 여기서 최저값 비교
            answer = Math.min(answer , Math.abs(startCnt - endCnt));
            
            // 붙이기
            List<Integer> startAddList = map.get(start);
            startAddList.add(end);
            map.put(start , startAddList);
            
            List<Integer> endAddList = map.get(end);
            endAddList.add(start);
            map.put(end , endAddList);
        }
        
        return answer;
    }
    // 전력망 연결하기
    public void input(int key , int value) {
        if (!map.containsKey(key)) {
            List<Integer> list = new ArrayList<>();
            list.add(value);
            map.put(key , list);
        } else {
            List<Integer> list = map.get(key);
            list.add(value);
            map.put(key , list);
        }
    }
    // dfs 메서드
    public int dfs(int start , int n) {
        int count = 0;
        
        boolean[] flag = new boolean[n];
        // stack 구축
        Stack<Integer> stack = new Stack<>();
        // 시작 전력망 넣기
        stack.add(start);
        
        while (!stack.isEmpty()) {
            // stack에서 꺼내기
            int num = stack.pop();
            // 방문처리
            flag[num - 1] = true;
            
            List<Integer> list = map.get(num);
            // 해당 전력망에 연결되어있는 리스트 돌기
            for (int i = 0; i < list.size(); i++) {
                // 방문처리 되어 있는 곳은 continue
                if (flag[list.get(i) - 1]) {
                    continue;
                }
                // 안되어 있는 곳은 add
                stack.add(list.get(i));
            }
            // count 증가
            count++;
        }
        
        return count;
    }
}

 

마치 BFS 알고리즘처럼 푸는 방식이다. 이렇게 되면 둘이 다른거 없지 않나? 싶다...