[알고리즘문제] 릿코드 Number of Provinces

leetcode.com/problems/number-of-provinces/

Number of Provinces - LeetCode

그래프가 주어진다.

각 노드는 하나씩 도시이다.

각 노드는 연결되어있을수도 있고 연결되지 않을수도 있다.

모두 연결되어있을 경우 하나의 도 라고 친다.

2차원 배열로 그래프가 주어질 때 총 도의 수를 반환하는 문제이다.

 

예시 1

예시2

#include<iostream>
#include<vector>

using namespace std;

class Solution {    
public:
    void dfs(int node, vector<vector<int>>& isConnected, vector<int>& visited) {
        visited[node] = 1;
        for (int i = 0; i < isConnected[node].size(); i++) {
            if (isConnected[node][i] == 1 && visited[i] == 0) {
                dfs(i, isConnected, visited);
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        //노드별로 방문여부를 저장하는 vector 초기화
        vector<int> visited(isConnected.size(), 0);        
        int answer = 0;
        for (int i = 0; i < isConnected.size(); i++) {
            if (visited[i] == 0) {
                dfs(i, isConnected, visited);
                answer++;
            }
        }
        return answer;
    }
};

int main() {
    vector<vector<int>> isConnected = {
        {1,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
        {0,1,0,1,0,0,0,0,0,0,0,0,0,1,0},
        {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,1,0,1,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,1,0,0,0,0,0,0,0,1,0,0},
        {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
        {0,0,0,1,0,0,0,1,1,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,1,1,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0},
        {0,0,0,1,0,0,0,0,0,0,0,1,0,0,0},
        {0,0,0,0,1,0,0,0,0,0,0,0,1,0,0},
        {0,1,0,0,0,0,0,0,0,0,0,0,0,1,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}
    };

    Solution s;
    
    cout << s.findCircleNum(isConnected);

	return 0;
}

dfs로 풀면 된다.

0,0을 root로 시작하여 각 노드를 순회하며 원소가 1인 row의 배열로 가서 순회하여 탐색을 마친다.

 

rust로 작성한 코드

struct Solution;

impl Solution {
    fn dfs(node : usize, is_connected: &Vec<Vec<i32>>, visited: &mut Vec<i32>) {
        visited[node] = 1;
        for i in 0 .. is_connected[node].len(){
            //print!("{}", is_connected[node][i]);
            if is_connected[node][i] == 1 && visited[i] == 0 {
                Self::dfs(i, &is_connected, visited);
            }
        }
    }
    pub fn find_circle_num(is_connected: Vec<Vec<i32>>) -> i32 {
        let mut visited : Vec<i32> = vec![0; is_connected.len()];
        let mut answer : i32 = 0;
        for i in 0 .. is_connected.len(){
            if visited[i] == 0 {
                Self::dfs(i, &is_connected, &mut visited);
                answer += 1;
            }
            //println!();
        }
        answer
    }
}
pub fn run(){
    // let mut is_connected: Vec<Vec<i32>> = Vec::new();
    // is_connected.push(vec![1, 1, 0]);
    // is_connected.push(vec![1, 1, 0]);
    // is_connected.push(vec![0, 0, 1]);

    let is_connected : Vec<Vec<i32>> = vec![
        vec![1,0,0,0,0,0,0,0,0,1,0,0,0,0,0],
        vec![0,1,0,1,0,0,0,0,0,0,0,0,0,1,0],
        vec![0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],
        vec![0,1,0,1,0,0,0,1,0,0,0,1,0,0,0],
        vec![0,0,0,0,1,0,0,0,0,0,0,0,1,0,0],
        vec![0,0,0,0,0,1,0,0,0,0,0,0,0,0,0],
        vec![0,0,0,0,0,0,1,0,0,0,0,0,0,0,0],
        vec![0,0,0,1,0,0,0,1,1,0,0,0,0,0,0],
        vec![0,0,0,0,0,0,0,1,1,0,0,0,0,0,0],
        vec![1,0,0,0,0,0,0,0,0,1,0,0,0,0,0],
        vec![0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
        vec![0,0,0,1,0,0,0,0,0,0,0,1,0,0,0],
        vec![0,0,0,0,1,0,0,0,0,0,0,0,1,0,0],
        vec![0,1,0,0,0,0,0,0,0,0,0,0,0,1,0],
        vec![0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
    ];

    println!("{}", Solution::find_circle_num(is_connected));
}