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

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

(그림 설명은 링크를 참고해주세요)

DFS의 전형적인 문제입니다. 부분 사각형을 구하는것도 비슷한 패턴이라고 생각이드네요.

 

먼저 방문을 했는지 체크할 visited boolean형 배열이 필요합니다. 컴퓨터를 방문했는지 하지 않았는지 계속해서 체크를 해주어야 하기 때문입니다. dfs 함수 안에서는 방문하지 않았을 경우 해당 컴퓨터와 연결되어 있는 컴퓨터를 방문합니다.

 

main 함수에서 for 반복문 안에 방문하지 않은 컴퓨터만 dfs 실행시키도록 되어있어 방문한 컴퓨터는 순회를 시작하지 않습니다. 즉 방문하지 않은 경우에만 정답인 answer를 증가시켜 준다면 하나로 연결된 네트워크 컴퓨터는 순회 자체를 하지 않아 정답 체크가 가능합니다.

 

아래는 소스코드 입니다.

 

public class Network {
    private int answer = 0;

    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                answer++;
                dfs(computers, visited, i);
            }
        }

        return answer;
    }

    public void dfs(int[][] computers, boolean[] visited, int computer) {
        if (visited[computer]) {
            return;
        }

        visited[computer] = true;
        for (int i = 0; i < computers[computer].length; i++) {
            if (computer == i) {
                continue;
            }

            if (computers[computer][i] == 1) {
                dfs(computers, visited, i);
            }
        }
    }