devFancy BE Developer

[Programmers] 43162. 네트워크(DFS)

2023-12-14
devFancy

문제 링크

성능 요약

  • 메모리: 71.4 MB, 시간: 0.10 ms

구분

  • 코딩테스트 연습 > 깊이/너비 우선 탐색 > 네트워크

Answer Code1(23.11.08)

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[computers.length];

        // 노드 방문 초기화
        for (boolean visit : visited) {
            visit = false;
        }

        for(int i = 0; i < computers.length; i++) {
            if(visited[i] == false) { // 해당 노드를 방문하지 않았을 경우
                answer++; // 새로운 네트워크 찾았으므로 +1 증가
                dfs(i, visited, computers);
            }
        }

        return answer;
    }
    // node: 현재 노드, visited: 방문여부, computers: 컴퓨터간의 연결 정보를 나타내는 2차원 배열
    public void dfs(int node, boolean[] visited, int[][] computers) {
        visited[node] = true;

        for(int i = 0; i < computers.length; i++) {
            // 아직 방문하지 않는 노드 && 현재 노드와 연결된 경우
            if(visited[i] == false & computers[node][i] == 1) {
                dfs(i, visited, computers);
            }
        }
    }
}

문제풀이(Answer Code1)

DFS에 대한 알고리즘 개념을 안 상태로 해당 문제에 접근하면,

(1) 처음에 노드 방문을 boolean 배열을 만들어서 컴퓨터의 개수(n)만큼 for문을 돌려서 초기화해주고,

(2) visited[i] 값이 false이면 깊이 우선 탐색(dfs) 메서드를 호출하고 answer++ 해준다.

(3) 전달받은 파라미터인 visited[i] 값을 true로 바꿔준다.

(4) computers[] 길이만큼 반복문들 돌면서

(5) 아래 조건을 모두 만족하면 재귀 호출을 한다.

  • 자기 자신이 아니며 (i != j)

  • visited 배열 i의 위치 값이 false이며

  • computers 배열의 값이 1인 것

(6) 2번으로 돌아간다.

(7) answer을 리턴한다.

Answer Code2(23.12.14)

// 프로그래머스 - 네트워크
class Solution {
    static boolean[] visited;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[computers.length];

        // 노드 방문 초기화
        for(boolean visit : visited) {
            visit = false;
        }

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

        return answer;
    }

    /*
     * node: 현재 노드
     * visited: 방문여부
     * computer: 컴퓨터간의 연결 정보를 나타내는 2차원 배열
     */
    public void dfs(int node, int[][] computers) {
        visited[node] = true;

        for(int i = 0; i < computers.length; i++) {
            if(visited[i] == false && computers[node][i] == 1) {
                dfs(i, computers);
            }
        }
    }
}

Review(23.12.14)

  • 첫번째 풀이와 다른 점은 visited 배열을 static으로 선언해서 dfs를 호출할 때, visited 매개변수를 없애주었다.

  • 해당 문제는 연결된 요소 찾기 유형과 흡사해서, 이전에 풀었던 문제와 비슷했지만, 아직은 익숙치 않아서 더 자주 풀어봐야겠다.

Reference

  • https://beaniejoy.tistory.com/41

Comments

Index