๊น์ด/๋๋น ์ฐ์ ํ์(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;
}
'๐ ์๊ณ ๋ฆฌ์ฆ > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/PGS] Lv.1 : ์ฒด์ก๋ณต (GREEDY) (0) | 2023.02.23 |
---|---|
[C++/PGS] Lv.3 : ๋ฑ๊ตฃ๊ธธ (DP) (1) | 2023.02.23 |
[C++/PGS] Lv.2 : ํ๊ฒ ๋๋ฒ (DFS) (0) | 2023.02.23 |
[C++/PGS] Lv.2 : ๊ฒ์ ๋งต ์ต๋จ๊ฑฐ๋ฆฌ (BFS) (0) | 2023.02.23 |
[PGS] Lv.0 (์ฝ๋ฉํ ์คํธ ์ ๋ฌธ) 12์ผ์ฐจ ๋ฌธ์ (0) | 2023.02.20 |