๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Programmers

[C++/PGS] Lv.3 : ๋„คํŠธ์›Œํฌ (DFS/BFS)

728x90

๊นŠ์ด/๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(DFS/BFS) : ๋„คํŠธ์›Œํฌ

๋ฌธ์ œ ์ถœ์ฒ˜ - ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๊ณ ๋“์  Kit

 

๋ฌธ์ œ ์„ค๋ช…

๋„คํŠธ์›Œํฌ๋ž€ ์ปดํ“จํ„ฐ ์ƒํ˜ธ ๊ฐ„์— ์ •๋ณด๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ๋„๋ก ์—ฐ๊ฒฐ๋œ ํ˜•ํƒœ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ปดํ“จํ„ฐ 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์ž…๋‹ˆ๋‹ค.


 

๋Š˜ ๊ทธ๋žฌ๋“ฏ์ด ์‚ฝ์งˆ ์—ด์‹ฌํžˆ ํ–ˆ๋‹ค

์ž…๋ ฅ ํ˜•์‹์ด matrix๋ผ์„œ bfs๋กœ ํ’€๋ฉด ๋˜๊ฒ ๊ตฌ๋‚˜~ํ•˜๋ฉด์„œ ํ’€๋‹ค๊ฐ€

์ฝ”๋“œ๊ฐ€ ๋„ˆ๋ฌด ๊ธธ์–ด์ ธ์„œ ๋•Œ๋ ค์น˜๊ณ 

dfs๋กœ ํ’€์—ˆ์Šต๋‹ˆ๋‹ค.

bfs / dfs ๋‘˜ ๋‹ค ํ’€์ด๊ฐ€ ๊ฐ€๋Šฅํ•˜๋˜๋ฐ.. dfs ์ฝ”๋“œ๊ฐ€ ํ›จ์”ฌ ์งง๊ณ  ๊ฐ„๋‹จํ•จ

 

์ผ๋ฐ˜์ ์œผ๋กœ ์ตœ๋‹จ๊ฑฐ๋ฆฌ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋Š” bfs๊ฐ€ ํŽธํ•˜๊ณ 

๋‹ค๋ฅธ๊ฑด ๋Œ€๋ถ€๋ถ„ dfs๊ฐ€ ํŽธํ•œ๋“ฏ.

 

1. matrix์— ์†์ง€ ๋ง๊ณ , visited๋Š” 1์ฐจ์› ๋ฐฐ์—ด๋กœ ์„ ์–ธํ•œ๋‹ค. ๊ทธ๋ƒฅ ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ๋งŒ ์ฒดํฌํ•˜๋ฉด ๋œ๋‹ค๊ตฌ
2. ํ˜„์žฌ ๋…ธ๋“œ์— ๋ฐฉ๋ฌธํ•œ ์  ์—†์œผ๋ฉด dfs ์‹คํ–‰
3. ๋ชจ๋“  ๋…ธ๋“œ ์ค‘์—์„œ ๋ฐฉ๋ฌธํ•œ ์  ์—†๊ณ  && ํ˜„์žฌ ๋…ธ๋“œ์™€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค๋ฉด ํƒ์ƒ‰ ๊ณ„์† ์‹คํ–‰!

 

 

 

๋‚˜์˜ ํ’€์ด

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int visited[202] = {0,};

void dfs(int n, vector<vector<int>> computers,int current){
    visited[current] = 1;
    for(int i=0; i<n; ++i){
        if(visited[i]==0 && computers[current][i]==1){
            dfs(n,computers,i);
        }
    }
}

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

 

728x90