[프로그래머스] 네트워크

[프로그래머스] 네트워크

728x90

반응형

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

풀이

두가지 방법의 풀이가 있다. Union-Find 알고리즘을 사용하는 방법과 BFS를 사용하는 방법 두가지가 있다.

1. Union-Find 알고리즘

인접행렬로 주어진 정보를 이용해서 i!=j && computers[i][j]==1 이라면 두 컴퓨터 사이에는 네트워크로 연결이 된것이므로, i와 j를 Union 해준다.

모든 노드들을 Union-Find 해준 뒤, 0~N-1번 노드를 탐색하며 큰 덩어리의 개수(i==parent[i] 인 노드의 개수) 를 세어준다.

2. BFS

모든 노드를 탐색하며, 탐색한 노드를 visited배열로 체크를 해주며, 방문하지 않은 노드이면서 현재 노드와 연결이 된 노드들을 탐색해준다. 모두 탐색을 하며 한번 BFS를 탐색할때마다 ANSWER+1을 해준다.

코드

1. Union-Find

class Solution { static int parent[]=new int[200]; public void init(int n){ for(int i=0;ib){ parent[a]=b; } else{ parent[b]=a; } } public int solution(int n, int[][] computers) { int answer = 0; init(n); for(int i=0;i

2. BFS

import java.util.*; class Solution { static boolean visited[]=new boolean[200]; public void bfs(int node,int n,int[][] computers){ Queue q=new LinkedList(); q.offer(node); visited[node]=true; while(!q.isEmpty()){ int now=q.poll(); for(int i=0;i

반응형

from http://khu98.tistory.com/305 by ccl(A) rewrite - 2021-11-19 20:27:05