[프로그래머스][JAVA] 9주차_전력망을 둘로 나누기 (그래프, DFS)

2021. 10. 29. 17:34· 알고리즘 풀이/프로그래머스
728x90

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.util.*;
 
class Solution {
    List<Node> nodeList;
    int nodeNum;
    int answer;
    boolean[] visited;
    
    class Node{
        int num;
        List<Integer> edge;
        
        Node(int num){
            this.num = num;
            edge = new ArrayList<>();
        }
        
    }
    
    public int solution(int n, int[][] wires) {
        nodeList = new ArrayList<>();
        answer = n;
        visited = new boolean[n+1];
        
        for(int i=0; i<=n; i++)
            nodeList.add(new Node(i));
        
        
        for(int[] wire : wires){
            int a = wire[0];
            int b = wire[1];
            nodeList.get(a).edge.add(b);
            nodeList.get(b).edge.add(a);
        }
        
        
        
        // wire끊기
        for(int[] wire : wires){
            Integer a = new Integer(wire[0]);
            Integer b = new Integer(wire[1]);
            nodeList.get(a).edge.remove(b);
            nodeList.get(b).edge.remove(a);
            
            // a에서 시작
            nodeNum = 0;
            DFS(a);
            // System.out.println("nodeNum^^ : "+ nodeNum);
            
            answer = Math.min(answer, Math.abs(2*nodeNum-n));
            
            nodeList.get(a).edge.add(b);
            nodeList.get(b).edge.add(a);
        }
            
        
        
        return answer;
    }
    
    private void DFS(int currNum){
        Node curr = nodeList.get(currNum);
        nodeNum++;
        visited[currNum] = true;
        
        for(int nodeNum : curr.edge){
            if(!visited[nodeNum]){
                DFS(nodeNum);
            }
            
        }
        
        
        visited[currNum] = false;
        
    }
}
Colored by Color Scripter
cs
저작자표시 (새창열림)

'알고리즘 풀이 > 프로그래머스' 카테고리의 다른 글

[프로그래머스][JAVA] 문자열 내 마음대로 정렬하기 (문자열)  (0) 2022.02.05
[프로그래머스][JAVA] 시저 암호 (문자열)  (0) 2022.02.04
[프로그래머스][JAVA] 8주차_최소직사각형 (수학)  (0) 2021.10.29
[프로그래머스][JAVA] 5주차_모음사전 (순열, 수학) #2  (0) 2021.10.28
[프로그래머스][JAVA] 단체사진 찍기 (순열)  (0) 2021.10.28
'알고리즘 풀이/프로그래머스' 카테고리의 다른 글
  • [프로그래머스][JAVA] 문자열 내 마음대로 정렬하기 (문자열)
  • [프로그래머스][JAVA] 시저 암호 (문자열)
  • [프로그래머스][JAVA] 8주차_최소직사각형 (수학)
  • [프로그래머스][JAVA] 5주차_모음사전 (순열, 수학) #2
배게
배게
배게
백엔드
배게
전체
오늘
어제
  • 분류 전체보기 (430)
    • 알고리즘 풀이 (338)
      • 백준 (167)
      • Codility (22)
      • 프로그래머스 (123)
      • LeetCode (2)
      • CodeForces (9)
      • SWEA (15)
    • 백엔드 (11)
    • Coding existing for (3)
    • 무지성 메모 (40)
    • Debug (30)
    • 자바 (8)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

인기 글

태그

  • 카톡 내보내기한 파일 정렬
  • 카카오톡
  • 카톡
  • hibernate
  • MYSQL
  • 카카오톡 txt파일 정렬

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
배게
[프로그래머스][JAVA] 9주차_전력망을 둘로 나누기 (그래프, DFS)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.