[프로그래머스]네트워크 문제풀이(DFS와 BFS)

DFS와 BFS

: 그래프의 주어진 모든 노드를 순회하기 위한 알고리즘! (순회하는게 목적..)

DFS(깊이우선탐색) 

• 개념 : DFS는 한 방향으로 갈 수 있는 깊이까지 탐색한다. 막 다른 곳에 도달하면 방문표시를 하고 가장 가까운 갈림길로 돌아와 다시 탐색을 시작한다. 이러한 방법으로 모든 그래프를 순회함! 
• 장점 및 단점 : DFS는 BFS보다 메모리는 유리하나 속도는 더 떨어짐
• 구현방법 :  Stack을 이용해 구현하거나 재귀함수를 이용해 구현할 수 있음  

 

[Stack을 이용하는 방법]

1. 시작 그래프를 출력 

2. 인접 노드를 모두 Stack에 넣음

3. Stack에서 노드를 하나 빼서 출력!

4. 인접 노드 중 출력된 적이 없는 노드 모두 Stack에 넣음 

5. Stack에서 노드를 하나 빼서 출력! 

.

.

.

=> 모든 노드가 출력 될때까지 반복 

 

[재귀함수를 이용하는 방법]

1. 시작노드를 출력! 

2. DFS(인접노드 중 방문한적 없는 노드) 를 Call

 

[재귀함수를 이용한 프로그래머스 네트워크 문제 풀이 방법]

public class Day1 {

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

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

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

    return answer;
  }

  private void dfs(int start, int[] visited, int[][] computers, int n) {

    visited[start] = 1;

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

  }


  @Test
  public void 정답() {
    Assert.assertEquals(2, solution(3, new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
    Assert.assertEquals(1, solution(3, new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}}));
  }
}

 

BFS(너비우선탐색)

개념 : 인접한 노드를 먼저 다 방문한 후 그 다음 노드를 방문함!

구현방법 : Queue를 이용해 구현할 수 있음. 

 

[Queue를 이용해 구현하는 방법]

1. 시작노드를 출력 

2. 시작노드에 인접한 노드 모두 Queue에 넣음 

3. Queue에서 노드를 하나 빼고 이를 출력함. 

4. 출력한 노드의 인접한 노드들 중 방문한적 없는 노드를 다시 Queue에 넣음 

5. Queue에서 노드를 하나 빼고 이를 출력함 .

.

.

.

-> 모든 노드를 순회할 때 까지 이를 반복

[Queue를 이용해 BFS로 프로그래머스 네트워크 문제 풀이]

public class Day2 {

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

    int answer = 0;
    int index = 0;
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();

    for (int i = 0; i < n; i++) {

      if (!visited[i]) {

        queue.add(i);
        answer++;

        while (!queue.isEmpty()) {

          index = queue.poll();
          visited[index] = true;

          for (int j = 0; j < n; j++) {
            if (computers[index][j] == 1 && visited[j] == false) {
              queue.add(j);
            }
          }
        }
      }
    }
    return answer;
  }


  @Test
  public void 정답() {
    Assert.assertEquals(2, solution(3, new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
    Assert.assertEquals(1, solution(3, new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}}));
  }
}

 

- 도움이 정말 많이 된 Youtube 영상 

https://www.youtube.com/watch?v=_hxFgg7TLZQ