프로그래머스 - 네트워크 (BFS/DFS)

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

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

 

간만에 DFS/BFS 문제를 해결해봤다.

간만에 풀다보니까 visited 배열을 생성하는 것도 까먹었다.. 진짜 한심..

처음에 일차원배열에 방문한 컴퓨터노드일때 체크를 하면서 짜는 코드를 짜봤는데 30점인가 밖에 못받았다.. 충격

 

간단하게 해설을 보고 그냥 정석대로 풀어아겠다,,

하고 기억을 더듬어서 bfs/dfs.... 비스무리하게 짜봤는데 다행히 코드 수정하고나선 성공했다!

[x][x] 이 배열의 값이 1이여서 이걸 처리하는걸 깜박해서 살짝 애먹었다.

그래서 값을 찾았을 경우는 visited의 [x][x] [y][y] 값또한 1로 바꿔줘야지 이어지지 않은 단일 노드의 개수 또한 잘 포함할 수 있었다.

 

class Solution {
    int[] arr;
    int[][] visited;
    int[][] nodes;
    int num;
    int answer = 0;

    public int solution(int n, int[][] computers) {
        //init
        arr = new int[n];
        visited = new int[n][n];
        num = n;
        nodes = computers;
        for (int i = 0; i < n; i++) {
            arr[i] = 0;
            for (int j = 0; j < n; j++) {
                visited[i][j] = 0;
            }
        }

        //start
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] != 0) {
                    continue;
                }
                if (computers[i][j] == 1) {
                    visited[i][j] = 1;
                    visited[i][i]=1;
                    visited[j][j]=1;
                    answer++;
                    find(j);
                }
            }
        }
        return answer;
    }

    public void find(int x) {
        for (int y = 0; y < num; y++) {
            if (nodes[x][y] == 1) {
                if (visited[x][y] != 0)
                    continue;
                visited[x][y] = 1;
                visited[x][x]=1;
                visited[y][y]=1;
                find(y);
            }
        }
    }
}