[Java : 프로그래머스] 네트워크

📝 문제

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

🎯 풀이

❌ 상하좌우 풀이

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        for(int x = 0; x < computers.length; x++){
          for(int y = 0; y < computers.length; y++){
            if(computers[x][y] == 1){
              DFS(x, y, computers);
              answer++;
            }
          }
        }

        return answer;
    }
    
    public void DFS(int x, int y, int[][] computers){
        if(x < 0 || y < 0 || x >= computers.length || y >= computers.length)
          return;

        if(computers[x][y] == 1){
          computers[x][y] = 0;
          DFS(x-1, y, computers);
          DFS(x+1, y, computers);
          DFS(x, y-1, computers);
          DFS(x, y+1, computers);
        }
    }
}

N*N 행렬 기준으로 상하좌우 DFS 탐색을 진행하면서
이어지는 ‘1’을 모두 ‘0’으로 바꿔주고,
DFS 탐색이 진행되는 횟수를 카운트해서 반환하는 코드였다.

“실패” 퍼레이드가 펼쳐졌는데, 그 이유는 매우 단순하게도
인접한 노드(1-2, 4-5, 9-8)간의 연결에는 이 코드가 동작되지만,
인접하지 못한 노드(1-9, 5-8)간의 연결은 이 코드가 판별을 못한다.
상하좌우 말고, 노드별 방문 기록을 이용하는 전통적인 DFS로 구현해보자.

---

⭕ 방문기록 풀이

class Solution {
    public int solution(int n, int[][] computers) {
        // 방문기록 배열, 네트워크 개수 변수.
        boolean[] visited = new boolean[n];
        int answer = 0;
        // 모든 노드 시작!
        for(int source = 0; source < computers.length; source++){
          if(!visited[source]){  // 방문기록이 없으면 네트워크 개수 증가시키고 DFS탐색.
            answer++;
            DFS(source, visited, computers);
          }
        }

        return answer;
    }
    
    public void DFS(int source, boolean[] visited, int[][] computers){
        visited[source] = true; // 방문체크.

        for(int destination = 0; destination < computers.length; destination++){
          // 연결은 되어 있는데, 아직 방문 안했다면 재귀탐색 시작.
          if(computers[source][destination] == 1 && !visited[destination])
            DFS(destination, visited, computers);
        }
    }
}

👏👏👏