알고리즘) 프로그래머스 DFS/BFS, 네트워크
프로그래머스 고득점 Kit - DFS/BFS
문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한사항
- 컴퓨터의 개수 n은 1이상 200 이하인 자연수입니다.
- 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
- i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
- computer[i][i]는 항상 1입니다.
입출력 예
| n | computers | return |
| 3 | [[1, 1, 0], [1, 1, 0], [0, 0, 1]] | 2 |
| 3 | [[1, 1, 0], [1, 1, 1], [0, 1, 1]] | 1 |
입출력 예 설명
예제 #1
아래와 같이 2개의 네트워크가 있습니다.
예제 #2
아래와 같이 1개의 네트워크가 있습니다.
풀이
(2020.04.21)
ArrayList를 이용해서 네트워크를 연결해준다음, 확인을 통해 갱신하면서 만들어진 네트워크들을 다시 한 번 ArrayList에 담았다. 이 크기를 리턴해주면서 네트워크의 갯수를 구해주었다. 간단한 문제라고 생각하고 접근했다가, 생각보다 까다로와서 시간이 조금 걸렸다. 코드에 주석이 있어서 이해하는데 어렵지는 않겠지만 주석이 없는 두 메소드를 간략하게 설명하고 싶다.
첫째, 처음 초기화를 해주는 inItNetWork를 통해 전체 네트워크를 담을 ArrayList를 만들어 준다. 이 때, 첫 네트워크에 0을 넣어주고 return했는데, 자기 자신은 네트워크에 포함이 되기 때문에 넣어줬다. 코드의 로직을 따라가다보면 쉽게 이해될 것이다.
둘째, serachNum 메소드이다. 해당 컴퓨터가 포함된 네트워크를 찾아, 그 네트워크의 index를 리턴해주는 메소드이다. 해당 컴퓨터가 네트워크에 등록되어 있지 않다면, -1을 리턴해주어 새로운 네트워크를 만들 수 있게 해줬다.
문제에 대한 이해력이랑 코드를 설계하는 능력이 아직도 많이 부족하다.. 조금 더 분발하자!!
(2020.06.05)
find-union, dfs 두 방법에 대해 각각 코드를 짜보았다.
처음 짤 때, ArrayList로 네트워크를 List로 구현해서 풀었었는데, 아마 시간이 오래걸렸을 것이다.
find-union과 dfs로 푸는데는 그리 오랜 시간이 걸리지 않았다.
이 문제에서는 dfs의 효율이 가장 좋은 것 같다.
코드 1
package programmers;
import java.util.ArrayList;
public class KitDBFSNetwork {
private static int solution(int n, int[][] computers) {
ArrayList<ArrayList<Integer>> networks = inItNetwork();
for(int i=0; i<n; i++) {
int idx = searchNum(networks,i); // i번째 컴퓨터가 포함된 네트워크 탐색
ArrayList<Integer> origin;
if(idx ==-1) { // 없으면 네트워크 생성
origin = new ArrayList<>();
origin.add(i);
} else { // 있으면 네트워크 가져오기
origin = networks.get(idx);
networks.remove(idx); // 해당 네트워크는 목록에서 제거
}
for(int j=0; j<computers[i].length; j++) {
if(i !=j && computers[i][j] ==1) { // i번째 컴퓨터에 연결된 j(target) 컴퓨터
int targetIdx = searchNum(networks, j); // target이 다른 네트워크랑 연결됐는지 확인
if(targetIdx != -1) { // target이 연결된 네트워크가 존재하면
ArrayList<Integer> network = networks.get(targetIdx); // 받아와서
for(int num : origin) {
if(!network.contains(num)) {
network.add(num); // 네트워크를 합쳐주고
}
}
origin = network; // origin 교체
networks.remove(targetIdx); // network 목록에서 제거
} else {
origin.add(j); // i에 j 연결
}
}
}
networks.add(origin); // 네트워크 리스트에 완성된 네트워크 추가
}
return networks.size();
}
private static ArrayList<ArrayList<Integer>> inItNetwork() {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
ArrayList<Integer> tmp = new ArrayList<>();
tmp.add(0);
result.add(tmp);
return result;
}
private static int searchNum(ArrayList<ArrayList<Integer>> networks, int num) {
int result =-1;
for(int idx=0; idx<networks.size(); idx++) {
if(networks.get(idx).contains(num)) {
result = idx;
break;
}
}
return result;
}
public static void main(String[] args) {
int n = 3;
int[][] computers = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
// int n = 3;
// int[][] computers = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
System.out.println(solution(n, computers));
}
}
코드 2
class Solution { // dfs
int[] visit;
public int solution(int n, int[][] computers) {
int answer = 0;
visit = new int[n];
for(int i=0; i<computers.length; i++) {
if(visit[i] ==0) {
dfs(i, computers);
answer++;
}
}
return answer;
}
private void dfs(int idx, int[][] computers) {
if(visit[idx] == 0) {
visit[idx] =1;
for(int i=0; i<computers[idx].length; i++) {
if(computers[idx][i] ==1 && visit[i] ==0) {
dfs(i, computers);
}
}
}
}
}
코드 3
import java.util.HashSet;
class Solution { // find - union
int[] parents;
public int solution(int n, int[][] computers) {
int answer = 0;
inItParents(n);
for(int i=0; i<computers.length; i++) {
for(int j=0; j<computers[i].length; j++) {
if(computers[i][j] ==1) {
if(find(i) != find(j)) {
union(i,j);
}
}
}
}
HashSet<Integer> set = new HashSet<>();
for(int num : parents) {
set.add(find(num));
}
return set.size();
}
private void inItParents(int n) {
parents = new int[n];
for(int i=0; i<n; i++) {
parents[i] = i;
}
}
private int find(int val) {
if(val == parents[val]) {
return val;
}
return parents[val] = find(parents[val]);
}
private void union(int val1, int val2) {
val1 = find(val1);
val2 = find(val2);
if(val1 != val2) {
parents[val2] = val1;
}
}
}