Typiler

네트워크 문제

문제설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.

입출력 예

입출력 예 설명

예제 #1

아래와 같이 2개의 네트워크가 있습니다.

예제 #2

아래와 같이 1개의 네트워크가 있습니다.

풀이방법

프로그래머스에서 제공하는 코딩테스트 연습문제 Level 3 의 문제입니다. 일단 네트워크 문제는 분류가 깊이/너비 우선 탐색(DFS/BFS)로 분류가 되어있습니다. 하지만 저는 이 문제를 Union-Find로 풀어보려 합니다. 왜냐하면 연결된 그룹을 찾는 문제이고 주어진 입력값으로 각 컴퓨터를 연결하여 집합으로 묶어주면 그 집합의 개수만 카운트 해주면 될 것 같아서 저는 Union-Find 로 풀어보았습니다.

https://tylee82.tistory.com/291

import java.util.*;

class Solution {
    
    static int[] uArr;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        uArr = new int[n+4];
        
        for(int i=0; i<n ; i++){
            for(int j=0; j<n ; j++){
                if(i==j) continue; // computer[i][i]는 항상 1 이기때문에 필요없음
                if(computers[i][j]==1){ // 연결된 컴퓨터끼리 Union 해줌
                    setUnion(i, j); 
                }
            }
        }
        
        // System.out.println("0:"+getFind(0));
        // System.out.println("1:"+getFind(1));
        // System.out.println("2:"+getFind(2));
        
        // 집합의 개수를 카운트하기위한 변수
        ArrayList<Integer> alist = new ArrayList<Integer>();
        for(int i=0; i<n ; i++){
            if( alist.contains(getFind(i)) ){
                // getFind로 찾은 집합의 우두머리가 이미 alist 변수에 있으면 pass
                continue;  
            } 
            else {
                // alist 에 없으면 추가
                alist.add(getFind(i));
            }
        }
        
        // 집합은 alist 의 size 이다.
        answer = alist.size();
        
        return answer;
    }
    
    public void setUnion(int i, int j){
        int a = getFind(i);
        int b = getFind(j);
        if(a == b) return;
        uArr[a] = b;
    }
    
    public int getFind(int tar){
        if(uArr[tar] == 0) return tar;
        int ret = getFind(uArr[tar]);
        uArr[tar] = ret;
        return ret;
    }
}

결과

동작방식

맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식입니다.

• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

시간복잡도

- 인접리스트 : O(|V| + |E|) (정점의 개수:V, 간선의 개수:E)

- 인접행렬 : O(V^2) (정점의 개수:V)

참고사이트

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

기본코드

입력값

코드

package study.graph;


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class DFS {
	static int[] used;
	static int[][] map;
	static int N, M;
	public static void main(String[] args) throws IOException{
		
		System.setIn(new FileInputStream("input\\dfs.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		used = new int[N+1];
		map = new int[N+1][N+1]; // 인접행렬을 이용하기 위한 2차원 배열 생성
		
		StringTokenizer st = null;
		for(int m=0; m<M; m++) {
			st = new  StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			map[a][b] = 1;
			map[b][a] = 1; //양방향이기 때문에..
		}
		
		System.out.print("그래프 DFS 방문 순서 : " );
		dfs(1);
		
		bw.close();
		br.close();
	}
	
	static void dfs(int point) {
		Stack<Integer> st = new Stack<Integer>();
		st.add(point);
		used[point] = 1; // 방문표시
		System.out.print( point + " ");
		
		while(!st.isEmpty()) {
			st.pop();
			for(int i=1; i<=N; i++) {
				if(map[point][i]==1 && used[i] == 0) {
					// 다음 노드와 연결되어 있고 아직 방문하지 않았으면 st에 넣고, 재귀실행
					st.add(i);
					used[i] = 1;
					dfs(i);
				}
			}
		}
		
	}
}