๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
โœจ Algorithm

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค/C++] ๋„คํŠธ์›Œํฌ

by nitronium102 2021. 8. 24.

๋ฌธ์ œ ์„ค๋ช…

๋„คํŠธ์›Œํฌ๋ž€ ์ปดํ“จํ„ฐ ์ƒํ˜ธ ๊ฐ„์— ์ •๋ณด๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ๋„๋ก ์—ฐ๊ฒฐ๋œ ํ˜•ํƒœ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ปดํ“จํ„ฐ A์™€ ์ปดํ“จํ„ฐ B๊ฐ€ ์ง์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด์žˆ๊ณ , ์ปดํ“จํ„ฐ B์™€ ์ปดํ“จํ„ฐ C๊ฐ€ ์ง์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์„ ๋•Œ ์ปดํ“จํ„ฐ A์™€ ์ปดํ“จํ„ฐ C๋„ ๊ฐ„์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์ •๋ณด๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์ปดํ“จํ„ฐ A, B, C๋Š” ๋ชจ๋‘ ๊ฐ™์€ ๋„คํŠธ์›Œํฌ ์ƒ์— ์žˆ๋‹ค๊ณ  ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ปดํ“จํ„ฐ์˜ ๊ฐœ์ˆ˜ n, ์—ฐ๊ฒฐ์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ๋‹ด๊ธด 2์ฐจ์› ๋ฐฐ์—ด computers๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋„คํŠธ์›Œํฌ์˜ ๊ฐœ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•˜์‹œ์˜ค.

 

์ œํ•œ์‚ฌํ•ญ

  • ์ปดํ“จํ„ฐ์˜ ๊ฐœ์ˆ˜ n์€ 1 ์ด์ƒ 200 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
  • ๊ฐ ์ปดํ“จํ„ฐ๋Š” 0๋ถ€ํ„ฐ n-1์ธ ์ •์ˆ˜๋กœ ํ‘œํ˜„ํ•ฉ๋‹ˆ๋‹ค.
  • i๋ฒˆ ์ปดํ“จํ„ฐ์™€ j๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์œผ๋ฉด computers[i][j]๋ฅผ 1๋กœ ํ‘œํ˜„ํ•ฉ๋‹ˆ๋‹ค.
  • computer[i][i]๋Š” ํ•ญ์ƒ 1์ž…๋‹ˆ๋‹ค.

 

์ž…์ถœ๋ ฅ ์˜ˆ

n  computers   return

3 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 2
3 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] 1

 

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์˜ˆ์ œ #1
์•„๋ž˜์™€ ๊ฐ™์ด 2๊ฐœ์˜ ๋„คํŠธ์›Œํฌ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.

์˜ˆ์ œ #2
์•„๋ž˜์™€ ๊ฐ™์ด 1๊ฐœ์˜ ๋„คํŠธ์›Œํฌ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.

 

ํ’€์ด

ํ•ต์‹ฌ์€ ๋„คํŠธ์›Œํฌ๊ฐ€ ๋ถ„๋ฆฌ๋˜์–ด ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ๊ฒƒ!

๊ฐ ์ปดํ“จํ„ฐ ๊ฐœ์ˆ˜๋งŒํผ for๋ฌธ์„ ๋Œ๋ฉด์„œ ์—ฐ๊ฒฐ๋œ ๋„คํŠธ์›Œํฌ๋ฅผ ๋ชจ๋‘ ๋Š์œผ๋ฉด ๋œ๋‹ค. ์ปดํ“จํ„ฐ ํ•˜๋‚˜ ํ™•์ธํ•  ๋•Œ๋งˆ๋‹ค ans๋ฅผ ์ฆ๊ฐ€์‹œ์ผœ์ค€๋‹ค. 

ex) ์˜ˆ์ œ 2 [[1, 1, 0], [1, 1, 1], [0, 1, 1]], isVisited[0, 1, 2]=false;

01. 1๋ฒˆ ์ปดํ“จํ„ฐ์™€ ์—ฐ๊ฒฐ๋œ ๋„คํŠธ์›Œํฌ ๋ชจ๋‘ ์‚ญ์ œ -> [1, 2] ์‚ญ์ œ, [2, 3] ์‚ญ์ œ

- isVisited[0] = true

- DFS ๊ฒฐ๊ณผ isVisited[1] = true, isVisited[2] = true;

02. 2๋ฒˆ ์ปดํ“จํ„ฐ ๊ฒ€์‚ฌ ํŒจ์Šค

03. 3๋ฒˆ ์ปดํ“จํ„ฐ ๊ฒ€์‚ฌ ํŒจ์Šค

 

#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX 201
bool isVisited[MAX] = {0, };
using namespace std;

void dfs(int start, int n, vector<vector<int>> computers) { 
    isVisited[start] = 1; // ๋ฐฉ๋ฌธ ํ‘œ์‹œ
    for(int i=0; i<n; i++) { 
    	// ํ˜„์žฌ ์ปดํ“จํ„ฐ์™€ ์—ฐ๊ฒฐ๋œ ์ปดํ“จํ„ฐ ์ค‘ ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ปดํ“จํ„ฐ๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ
        // dfs ๋Œ๋ฉด์„œ ๋„คํŠธ์›Œํฌ๋ฅผ ๋Š์–ด์ค€๋‹ค. 
        if(isVisited[i] == 0 && computers[start][i] == 1) { 
            dfs(i, n, computers); 
        }
    } 
}

void bfs(int start, int n, vector<vector<int>> computers){
    queue<int> q;
    
    q.push(start);
    isVisited[start] = 1; // ๋ฐฉ๋ฌธ ํ‘œ์‹œ
    
    while(!q.empty()){
        int front = q.front();
        q.pop();
        
        for (int i=0; i<n; i++){
           if (isVisited[i] == 0 && computers[front][i] == 1){
               isVisited[i] = true;
               q.push(i);
           }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer=0;
    for (int i=0; i<n; i++){
        if (isVisited[i] == false){
            bfs(i, n, computers);
            answer++;
        }
    }
    return answer;
}

 

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

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋„คํŠธ์›Œํฌ

๋„คํŠธ์›Œํฌ๋ž€ ์ปดํ“จํ„ฐ ์ƒํ˜ธ ๊ฐ„์— ์ •๋ณด๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ๋„๋ก ์—ฐ๊ฒฐ๋œ ํ˜•ํƒœ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ปดํ“จํ„ฐ A์™€ ์ปดํ“จํ„ฐ B๊ฐ€ ์ง์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด์žˆ๊ณ , ์ปดํ“จํ„ฐ B์™€ ์ปดํ“จํ„ฐ C๊ฐ€ ์ง์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ

programmers.co.kr


์„ค๋ช… ์ฐธ๊ณ  https://eory96study.tistory.com/32

 

๋„คํŠธ์›Œํฌ - c++ (DFS/BFS)

https://programmers.co.kr/learn/courses/30/lessons/43162 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋„คํŠธ์›Œํฌ ๋„คํŠธ์›Œํฌ๋ž€ ์ปดํ“จํ„ฐ ์ƒํ˜ธ ๊ฐ„์— ์ •๋ณด๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ๋„๋ก ์—ฐ๊ฒฐ๋œ ํ˜•ํƒœ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ปดํ“จํ„ฐ A์™€ ์ปดํ“จํ„ฐ B๊ฐ€ ์ง..

eory96study.tistory.com

 

๋Œ“๊ธ€