네트워크(프로그래머스, Java)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크 | 프로그래머스

알고리즘 설명:

이미지 영역을 찾는 문제는 좌표에서 상하좌우로 1씩 들려가며 BFS탐색을 했다면 이번 문제에서는 그래프에서 탐색을 하는 경우이다.

• 큐(Queue)를 배열로 만들어 각 노드에 연결되어 있는 값들을 큐(Queue) 배열에 큐(Queue)로 넣어주었다.

• visit 배열로 방문여부를 관리하였고 탐색할 때 사용할 큐(Queue)하나를 더 생성하였다.

• 모든 노드들을 방문해야하므로 for문을 사용하여 방문 안된 경우에 탐색할 때 사용하려고 만든 큐에 값을 넣어주도록 하였다.

• 큐에 값이 들어간 후에 while문이 돌면서 연결되어 있는 노드들을 탐색하고 visit 배열을 업데이트 시켜준다.

• 위 for문이 돌면서 아직 방문이 안된 부분을 찾는다면 while문에서 탐색이 안된 경우이다. 즉 새로운 연결노드를 발견한 것이다. -> 이러한 경우를 체크!

막혔던 지점:

처음에는 DFS탐색방법을 이용하여 문제를 접근했지만 너무 복잡하여 빠르게 BFS탐색방법으로 갈아탔다.

BFS는 영역탐색, 목적지 최단거리, 경로등을 찾을 때 유용한 것 같고 DFS는 모든 경우의 수를 알아볼 때 유용한 것 같다.

package test;

import java.util.LinkedList;
import java.util.Queue;

public class Network {

	public static int solution(int n, int[][] computers) {
		Queue<Integer>[] queueComputers = new LinkedList[n];
		for (int i = 0; i < n; i++) {
			queueComputers[i] = new LinkedList();
			for (int j = 0; j < n; j++) {
				if (computers[i][j] == 1)
					queueComputers[i].offer(j);
			}
		}
		boolean[] visit = new boolean[n];
		int count = 0;

		Queue<Integer> queue = new LinkedList<>();

		for (int i = 0; i < visit.length; i++) {

			if (!visit[i]) {
				queue.offer(i);
				visit[i] = true;
				count++;
			}

			while (!queue.isEmpty()) {
				int s = queue.poll();

				while (!queueComputers[s].isEmpty()) {
					int it = queueComputers[s].poll();

					if (!visit[it]) {
						visit[it] = true;
						queue.offer(it);
					}
				}

			}
		}

		return count;
	}

	public static void main(String[] args) {
		int n = 4;
		int[][] computers1 = { { 1, 0, 0 }, { 0, 1, 1 }, { 0, 0, 1 } };
		int[][] computers2 = { { 1 } };
		int[][] computers3 = { { 1, 1, 1, 1 }, { 1, 1, 1, 0 }, { 1, 1, 1, 0 }, { 1, 0, 0, 1 } };
		System.out.println(solution(n, computers3));

	}

}