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

➡️문제 링크

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

 

 

💡아이디어

BFS, DFS, 그래프탐색!

 

사실 알고리즘고득점 kit의 깊이/너비 우선 탐색(DFS/BFS)에 있는 문제여서

문제의 유형이 무엇인지는 이미 알고 있었다

 

그래도 문제에서

"컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 

컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 

컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 

따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다."

 

라는 부분을 읽고, 

타고타고가 가능하네?

-> 그럼 1부터 N까지 각 정점을 탐색하면서 하나의 정점에서 방문할 수 있는 노드를 다 방문하자

-> 이때, 1~N 방문하면서 방문하지 않은 노드가 몇 번 나오는지 보자

-> 이게 문제에서 구해야하는 네트워크 수다!

이렇게 아이디어를 생각했다

 

 

말만 네트워크지

DFS,BFS 문제를 풀며 많이 봤던 영역 개수 구하기? 유형의 문제와 비슷하다고 생각해서

문제를 읽으며 이거 영역 구하기네!했다

 

 

✏️문제 풀이

1. BFS -  성공 

1~N까지 각 정점을 방문하면서, 해당 정점을 아직 방문하기 전이라면 BFS를 돌렸다.

 

지금 코드를 다시 보니,

"자기자신 제외" 는 어차피 visited 배열을 통해 방문 여부를 확인하기때문에 필요가 없는 것 같다.

/*
-> 영역 구하기
1. 1~n까지 bfs 돌려서 연결연결 visited 배열 표시하기
2. 1의 과정거치면서 방문하지 않은 경우-> 네트워크 1증가
*/

import java.util.*;

class Solution {
    boolean [] visited;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n];
        
        for(int i = 0; i< n; i++){
            if(!visited[i]){
                bfs(i, n, computers);
                answer++;
            }
        }
        return answer;
    }
    
    void bfs(int start, int n, int [][] computers){
        visited[start] = true;
        Queue<Integer> que = new LinkedList<>();
        que.add(start);
        
        while(!que.isEmpty()){
            int cur = que.poll();
            
            for(int j = 0; j < n; j++){
                if(cur != j){   // 자기자신 제외
                    if(computers[cur][j] == 1 && !visited[j]){
                        visited[j] = true;
                        que.add(j);
                    }
                }
            }
        }
    }
}

 

 

 

 

2. DFS - 성공

BFS와 똑같고, 대신 재귀를 이용해서 풀었다.

1~N까지 각 정점을 방문하면서, 해당 정점을 아직 방문하기 전이라면 DFS를 돌렸다.

/*
-> 영역 구하기
1. 1~n까지 dfs 돌려서 연결연결 visited 배열 표시하기
2. 1의 과정거치면서 방문하지 않은 경우-> 네트워크 1증가
*/

import java.util.*;

class Solution {
    boolean [] visited;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n];
        
        for(int i = 0; i< n; i++){
            if(!visited[i]){
                dfs(i, n, computers);
                answer++;
            }
        }
        return answer;
    }
    
    void dfs(int start, int n, int [][] computers){
        visited[start] = true;
        
        for(int j = 0; j < n; j++){
            if(computers[start][j] == 1 && !visited[j]){
                dfs(j, n, computers);
            }
        }
    }
}

 

 

 

 

 

+)

개인적으로 프로그래머스는 나에게 벽이 있는(?) 알고리즘 문제라고 생각해

Lv3인데 내가 풀 수 있을까..? 라는 마음에 풀기전부터 약간 쫄았다ㅎㅎ

근데 문제를 읽으니 이거 어디서 많이 본 유형이잖아! 하고

아이디어가 바로 떠올라 빠르게 풀 수 있었다

뭐든 하기 전에 겁 먹는 건 좋지 않은 것 같다!