99클럽 코테 스터디 15일차 TIL: [프로그래머스] 주식가격

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

프로그래머스

 

dfs로 아주 간단하게 풀 수 있는 문제다.

• 이차원 배열을 순회한다. 이때 아직 방문하지 않았으면서 값이 1이면 dfs를 시작한다.
• dfs를 통해 이어진 모든 노드들을 방문한다.
• dfs를 수행한 횟수가 네트워크 개수가 된다.

import java.util.*;

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