[프로그래머스/LV3] - 네트워크 (DFS, Union-Find 2가지 풀이)

About this offer

문제 풀이 DFS Union-Find 1. DFS class Solution { int[][] computers; int n; boolean[] visited; public int solution(int n, int[][] computers) { this.computers = computers; this.n = n; this.visited = new boolean[n]; int answer = 0; for(int i = 0; i < n; i++) { if(!visited[i]) { dfs(i); answer++; } } return answer; } void dfs(int cur) { visited[cur] = true; for(int next = 0; next < n; next++) { if(computers[cur][next] == 1 && !visited[next]) { dfs(next); } } } } DFS 풀 때 저만의 팁이 있다면 파라미터에는 변하는 값들만 들어가도 된다 라고 생각하니 다음부터는 편하게 풀리더라구요. 파라미터에 뭘 넣어야할지 고민하지 않고 변하지 않는 값들은 전부 멤버 변수로 빼서 풀었습니다. 2. Union-Find class Solution { int[] parent; public int solution(int n, int[][] computers) { int answer = 0; parent = new int[n]; for(int i = 0; i < n; i++) { parent[i] = i; } for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(computers[i][j] == 1) { union(i, j); } } } for(int i = 0; i < n; i++) { if(parent[i] == i) answer++; } return answer; } void union(int a, int b) { // 서로 공통 조상이 다른 경우 합치기 가능 if(find(a) != find(b)) { parent[find(a)] = find(b); } } // 루트 찾기 int find(int x) { // 재귀로 x의 루트를 끝까지 찾아낸다. 경로 압축 if(parent[x] != x) // 조건문 작성하지 않으면 무한 루프 { parent[x] = find(parent[x]); } return parent[x]; } } Union-Find는 섬 연결하기 문제에서도 사용가능하니 알아두면 좋습니다. 그래프 그룹(연결 요소, Connected Component) 개수 찾을 때 사용할 수 있다고 생각하면 됩니다.

Offer details

Provider

velog

Source

velog-rss

Score

54.35

Confidence

49%