프로그래머스] 네트워크

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

프로그래머스

 

 

풀이

dfs또는 bfs가 몇번동작하는 문제 

백준의 촌수 구하는 문제와 비슷.

 

문제는 간선의 정보를 주는것이 아니라 인접행렬을 전달해준다.

 

매번 간선의정보를 받아 인접리스트를 만들어서 사용했었다.

 

1. 인접행렬을 인접리스트로 바꿔서 푸는 방법

 

2. 인접행렬로 푸는 방법을 시도한다.

 

인접리스트 또는 인접행렬의 전체를 순회하며 방문한 노드인지 확인한다.

 

 

 

 

1. 인접행렬을 인접리스트로 바꿔서 푸는 방법

import java.util.*;

class Solution {
    /*
        dfs 도는 bfs가 몇번 동작하는지 체크하는 문제 -> 백준의 촌수구하는 문제
        인접배열 -> 인접리스트로 변환 
    */
    
    static List<Integer>[] graph;
    
    static boolean[] visited;
    
    static int count =0;
    
    
    public int solution(int n, int[][] computers) {
        
        graph = new ArrayList[n+1];
        visited = new boolean[n+1];
        
        for(int a=1;a<n+1;a++)
        {
            graph[a] = new ArrayList<>(); // 그래프 초기화
        }
        
        //인접리스트를 이용하여 그래프 생성
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==j) // 인접리스트에는 인접노드만 
                {
                    continue;
                }
                if(computers[i][j] == 1)
                {
                    graph[i+1].add(j+1);
                }
                
            }
        }
        
        for(int i=1;i<=n;i++)
        {
            if(!visited[i])
            {
                dfs(i);
                count++;
            }
            // System.out.println(graph[i].toString());
        }
        

        return count;

        
    }
    
    static void dfs(int node)
    {

        for(int adjNode : graph[node])
        {
            if(!visited[adjNode])
            {
                visited[adjNode] = true;
                dfs(adjNode);
            }
        }

    }
    

    
}

인접리스트 (그래프)에는 인접노드만 저장해준다.

 

2. 인접행렬을 이용하여 풀이

2차원배열의 모든 행을 순회하면서 dfs를 시도한다.

 

dfs안에서는 해당 행의 모든 열을 체크한다.

 

import java.util.*;

class Solution {
    
    static boolean[] visited;
    
    static int count =0;
    
    
    public int solution(int n, int[][] computers) {
        
        visited = new boolean[n+1];
        
        // 인접행렬 이용
        for(int i=0;i<n;i++)
        {
            if(!visited[i+1])
            {
                visited[i+1] = true;
                dfs2(i,n,computers);
                count++;
            }
        }
        
        return count;
    }

    static void dfs2(int node, int n, int[][] computers)
    {
        for(int i=0;i<n;i++)
        {
            if(computers[node][i] == 1 && !visited[i+1])
            {
                visited[i+1] = true;
                dfs2(i,n,computers);
            }
        }
    }

    

    
}