프로그래머스 - 네트워크(DFS/BFS 두가지 풀이 법)

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

코딩테스트 연습 - 네트워크

프로그래머스 네트워크 문제입니다.

DFS, BFS로 두가지 방법으로 풀어보았습니다.

소스의 BFS 매서드 사용부분에 DFS 매서드를 사용해도 정답이 나옵니다.

import java.util.LinkedList;
import java.util.Queue;

public class 네트워크2 {

    class Solution {

        boolean[] visited;

        public int solution(int n, int[][] computers) {

            visited = new boolean[n];
            int answer = 0;

            for(int i=0; i<visited.length; i++){

                if(visited[i] == false){
                    answer++;
                    BFS(i,computers);
                }

            }

            return answer;
        }

        void DFS(int start, int[][] map){

            visited[start] = true;

            for(int i=0; i<visited.length; i++){
                if(visited[i] == false && map[start][i] == 1){
                    DFS(i, map);
                }

            }

        }

        void BFS(int start, int[][] map){

            Queue<Integer> queue = new LinkedList<>();
            queue.add(start);

            while(!queue.isEmpty()){
                int index = queue.poll();
                visited[index] = true;

                for(int i=0; i<visited.length; i++){
                    if(visited[i] == false && map[index][i] == 1){
                        queue.offer(i);
                    }
                }


            }


        }

    }
}

 

노드를 모두 방문해야 하기 때문에 반복문의 코드와 인덱스를 잘 설정해주는 것이 무엇보다 중요합니다.

 

DFS, BFS 참고 : https://manducku.tistory.com/23