๋คํธ์ํฌ๋ ์ปดํจํฐ ์ํธ ๊ฐ์ ์ ๋ณด๋ฅผ ๊ตํํ ์ ์๋๋ก ์ฐ๊ฒฐ๋ ํํ๋ฅผ ์๋ฏธํฉ๋๋ค. ์๋ฅผ ๋ค์ด, ์ปดํจํฐ 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์ ๋๋ค.
๐ก BFS
๐ก ์ปดํจํฐ 0์์ ์์ํด์, ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ๋ฅผ ๋ชจ๋ queue์ ๋ฃ์
๐ก ์ฐ๊ฒฐ๋์ด ์์ง ์์ ์ปดํจํฐ๋ค์ด ์์ผ๋ฉด, count๋ฅผ ํ๊ณ ๋ค์ ์๋ก์ด queue๋ฅผ ์์ฑํด ๋ฐ๋ณตํจ
1) ์ปดํจํฐ 0์์ ์์ํด์, ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ๋ฅผ ๋ชจ๋ queue์ ๋ฃ์
while(!q.isEmpty()){
int now = q.poll();
for(int idx=0; idx<n; idx++){
if(computers[now][idx] == 1 && visited[idx] == false){
visited[idx] = true;
q.add(idx);
}
}
}
2) ์ฐ๊ฒฐ๋์ด ์์ง ์์ ์ปดํจํฐ๋ค์ด ์์ผ๋ฉด, count๋ฅผ ํ๊ณ ๋ค์ ์๋ก์ด queue๋ฅผ ์์ฑํด 1)์ ๋ฐ๋ณตํจ
for(int i=0; i<n; i++){
if(visited[i] == false) {
bfs(n,computers,i);
answer++;
}
}
import java.util.Queue;
import java.util.LinkedList;
class Bruteforce_2 {
static boolean[] visited;
public int solution(int n, int[][] computers) {
int answer = 0;
visited = new boolean[n];
for(int i=0; i<n; i++){
if(visited[i] == false) {
bfs(n,computers,i);
answer++;
}
}
return answer;
}
public void bfs(int n, int[][] computers, int i){
Queue<Integer> q = new LinkedList<>();
q.add(i);
while(!q.isEmpty()){
int now = q.poll();
for(int idx=0; idx<n; idx++){
if(computers[now][idx] == 1 && visited[idx] == false){
visited[idx] = true;
q.add(idx);
}
}
}
}
}
์ฑ๊ณตโจ