문제#
- 링크로 대체
풀이 및 주저리..
BFS 를 연습하고자 풀어본 문제이다. 생각보다 머리속에서 정리가 잘되어서 쉽게 풀 수 있었다. 갈 수 있는 곳의 위치들을 계산하고 하나씩 큐에 넣어가면서 그곳에서 새롭게 갈 수 있는 곳들을 검사해주는 방식으로 네트워크가 몇개 이루어져있는지 구해주었다.
코드
package programmers.school.day03;
import java.util.LinkedList;
import java.util.Queue;
public class Network {
// 먼저 배열의 값만큼 boolean 배열을 만들어주고 하나씩 값을 넣고
// 거기에 연결되어있는 배열로 들어가 찾기 (BFS)
public int solution(int n, int[][] computers) {
boolean[] isVisted = new boolean[n];
int answer = 0;
Queue<Integer> que = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
if (isVisted[i])
continue;
isVisted[i] = true;
que.add(i);
answer++;
while (!que.isEmpty()) {
int[] conn = computers[que.poll()];
for (int j = 0; j < conn.length; j++) {
if(conn[j] == 1 && !isVisted[j]) {
isVisted[j] = true;
que.add(j);
}
}
}
}
return answer;
}
}기억에 남길 것!
- 무