[프로그래머스] 위클리챌린지 9주차 전력망을 둘로 나누기(완성)

https://programmers.co.kr/learn/courses/30/lessons/86971?language=java 

코딩테스트 연습 - 9주차

 

안 그래도 요즘 백준에서도 DFS, BFS 문제를 풀고 있는데 관련된 문제가 위클리챌린지로 나온 것 같다. 다만 아직 해결못한 테스트케이스가 있어서 추후에 해결하려고 한다. 런타임 에러라고 나오는 걸 보니 해결방법 자체가 틀렸다기보다는 인덱스나 변수 사이즈 등 기타 신경 못 쓴 부분이 있다고 생각된다.

원인을 몰라서 프로그래머스 질문하기 게시판에 글을 올렸었는데 다른 분이 답글을 달아주셔서 금방 해결할 수 있었다.다. 일단 해결방법은 찾아서 제출은 완료했고, 원인을 찾아보니 결국 정렬하는 부분이 문제였었다. 만약 차이가 같은 경우가 있으면 이 부분도 정렬에 대한 정의를 해줬어야 하는데 이 부분을 처리하지 않아서 에러가 뜬 거였다. (정권호님 감사합니다! https://programmers.co.kr/questions/20975)

 

 

1.  파라미터로 입력 받은 wires 배열로 받은 값을 graph 배열 값으로 넣어주고, dfs 실행을 위한 초기값을 설정해준다.

2.  wires의 인덱스에 따라 하나씩 값을 없애고 dfs를 실행한다.

     2-1. dfs를 실행할 송전탑을 기준으로, Stack을 사용해 몇 개의 송전탑이 연결되었는 지 확인한다.

     2-2. 전체 갯수(n)는 입력으로 주어지므로, 연결된 송전탑과 전체 개수에서 연결된 송전탑을 뺀 차이를 구할 수 있다.

     2-3. ArrayList를 사용해서 해당 시작인덱스(i)와 차이값을 넣어준다.

3. Collections.sort를 이용해 차이값을 기준으로 오름차순 정렬해서 그 값을 리턴한다.

     3-1. 예외 : n==2일 경우에는 송전탑이 무조건 2개이기 때문에 그 차이는 0으로 예외처리해준다.

 

---

문제 및 제한조건

---

예제

 

---

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;

class Solution
{
    public static void dfs(ArrayList<int[]> list, Stack<Integer> s, int[][] graph, boolean[] visit, int n, int start)
    {
        int cnt = 0;
        s.add(start);
        visit[start] = true;
        
        // dfs 실행
        while(!s.isEmpty())
        {
            cnt++;
            int index = s.pop();
            
            for(int i=0; i<graph[index].length; i++)
            {
                if(graph[index][i]!=0 && !visit[i])
                {
                    visit[i] = true;
                    s.add(i);
                }
            }
        }
        
        // 없앤 송전탑의 인덱스를 기준으로, 양 송전탑 집합의 개수 차이를 리스트에 삽입
        list.add(new int[]{start, Math.abs(cnt-(n-cnt))});
    }
    public int solution(int n, int[][] wires)
    {
        // 예외처리 : 송전탑이 2개일 경우 무조건 0 출력
        if(n==2)
        {
            return 0;
        }
        
        // dfs 실행을 위한 초기값 설정
        boolean[] visit = new boolean[n];
        int[][] graph = new int[n][n];
        Stack<Integer> s = new Stack<Integer>();
        ArrayList<int[]> list = new ArrayList<int[]>();
        
        // wires 배열로 받은 값을 graph 배열로 설정
        for(int i=0; i<wires.length; i++)
        {
            graph[wires[i][0]-1][wires[i][1]-1] = 1;
            graph[wires[i][1]-1][wires[i][0]-1] = 1;
        }
        
        for(int i=0; i<wires.length; i++)
        {
            // wires의 인덱스에 따라 하나씩 값을 없애고 dfs 실행
            graph[wires[i][0]-1][wires[i][1]-1] = 0;
            graph[wires[i][1]-1][wires[i][0]-1] = 0;
            dfs(list, s, graph, visit, n, i);
            
            // 값을 없애기 전 단계로 초기화 설정
            Arrays.fill(visit, false);
            graph[wires[i][0]-1][wires[i][1]-1] = 1;
            graph[wires[i][1]-1][wires[i][0]-1] = 1;
        }
        
        // 송전탑 집합의 차를 기준으로 오름차순 정렬
        Collections.sort(list, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2)
            {
                if(o1[1]!=o2[1])
                {
                    return o1[1]>o2[1]==true?1:-1;
                }
                else
                {
                    return 0;
                }
            }
        });
        
        // 제일 차이가 적은 값을 출력
        return list.get(0)[1];
    }
}