본문 바로가기
JAVA/알고리즘

[ 깊이/너비 우선 탐색(DFS/BFS) Level3 ] 프로그래머스 네트워크 - 자바 Java

by hak0205 2020. 8. 18.
반응형

출처 : https://programmers.co.kr/learn/courses/30/lessons/43162

 

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


해당 문제는 깊이 우선 탐색 문제입니다. 여기서 깊이 우선 탐색(DFS)이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다.

 

네트워크 자바 코드

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean visited[] = new boolean[n + 1];
        for (int i = 0; i < n; i++) {
            if (visited[i] == false) { //방문을 안했다면 dfs로 검색합니다.
                answer += dfs(i, computers, visited);
            }
        }
        return answer;
    }

    public static int dfs(int x, int[][] computers, boolean[] visited) {
        if (visited[x]) {
            return 0;
        }
        visited[x] = true; //방문여부 체크
        
        for (int y = 0; y < computers[x].length; y++) {
        	//연결이 되어있고 방문을 아직안했다면
            if (computers[x][y] == 1 && visited[y] == false) {
                dfs(y, computers, visited);
            }
        }
        return 1;
    }
}

정리

DFS에서는 백트래킹 기법을 사용합니다. 백트래킹 기법은 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다.

 

즉, 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아갑니다. 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다.

 

그리고 DFS에서 체크포인트 2가지는 방문 여부(visited)와 검사하려는 값의 연결여부(1)입니다. 방문을 했거나 또는 연결이 안 되어있다면 검사할 필요가 없습니다.

 

감사합니다.

 
 
 
반응형

댓글