99클럽 코테 스터디 31일차 TIL [DFS, BFS]

- 오늘의 학습 키워드 : DFS, BFS

[문제 이름 : 네트워크 (프로그래머스, Lv 3)]

문제 url : https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/description/

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    static Queue<Integer> queue = new LinkedList<>();
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n];
        int answer = 0;
        
        // dfs 풀이 방법
        // for(int i=0; i<n; i++) {
        //     if(!visited[i]) {
        //         answer++;
        //         dfs(i, visited, computers);
        //     }
        // }
        
        // bfs 풀이 방법
        for(int i=0; i<n; i++) {
            if(!visited[i]) {
                answer++;
                bfs(i, visited, computers);
            }
        }

        return answer;
    }
    
    private void dfs(int now, boolean[] visited, int[][] computers) {
        visited[now] = true;
        for(int i=0; i<computers.length; i++) {
            if(!visited[i] && computers[now][i] == 1) {
                dfs(i, visited, computers);
            }
        }
    }
    
    private void bfs(int now, boolean[] visited, int[][] computers) {
        queue.offer(now);
        visited[now] = true;
        
        while(!queue.isEmpty()) {
            int node = queue.poll();
            for(int i=0; i<computers.length; i++) {
                if(!visited[i] && computers[node][i] == 1) {
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }
    }
}

[풀이 과정]

1. 방문 여부를 저장하는 visited 배열을 생성한다.

2. n의 길이만큼 순회하며, 방문하지 않은 컴퓨터를 찾는다.

3. dfs, bfs를 돌면서, 방문 여부를 체크하며 연결된 네트워크를 찾아나간다.

 

dfs, bfs를 풀어본 사람이라면 어렵지 않게 풀 수 있는 문제였다. 두 방법으로 모두 구현해보았다.

풀이 시간 : 30분