LEVEL 3 : 네트워크

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

코딩테스트 연습 - 네트워크

 

• 문제

  • 

    문제

---

풀이

• BFS로 연결된 네트워크 개수를 세는 문제이다.
• 방문 여부를 계산할 N길이의 Visit 배열을 선언 후 연결된 네트워크 체크
• bfs 함수를 통해 해당 노드번호와 연결된 모든 노드의 방문 상태를 TRUE로 바꾸어 준다.
• bfs 함수
  
  • 연결된 노드들의 담기위한 Queue를 선언한다.
  • 시작 노드의 방문 상태를 TRUE로 바꾼 뒤, Queue에 시작 노드를 넣어준다.
  • Queue에서 데이터를 꺼내면서, 꺼낸 데이터와 연결된 모든 노드 중 방문하지 않은 노드를 방문처리 후 큐에 넣어준다.
  • Queue가 빌 때까지 반복한다.

• public static boolean[] visit;
  	public static int solution(int n, int[][] computers) {
  		visit = new boolean[n];//방문여부를 표시할 배열
  		int answer = 0;//네트워크 갯수
  		for(int i=0;i<n;++i) {
  			if(!visit[i]) {//방문하지 않은 노드일 경우
  				answer++;
  				bfs(computers,n,i);//연결된 모든 노드 방문처리
  			}
  		}
  		return answer;
  	}
  	private static void bfs(int[][] computers, int n,int start) {
  		Queue<Integer> que = new LinkedList<>();
  		visit[start] = true;//시작노드를 방문처리 후,
  		que.offer(start);//큐에 넣어준다
  		while(!que.isEmpty()) {// 큐에 데이터가 없을 때 까지
  			int now = que.poll();//큐에서 데이터를 꺼내
  			for(int i=0;i<n;++i) {
  				if(computers[now][i] == 1 && !visit[i]) { //연결되고, 방문하지 않은 노드를
  					visit[i] = true;//방문처리 후
  					que.offer(i);//큐에 넣는다
  				}
  			}
  		}
  	}