프로그래머스 (Level 3) - 네트워크

문제 설명

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

 

풀이 

연결된 컴퓨터에 대한 정보로 그래프를 생성한 후 DFS 또는 BFS 알고리즘을 사용해서 그래프 내 네트워크의 개수를 구하면 되는 문제이다.

 

/* 그래프의 각 노드에 대한 정보를 정의 */
class Node {
    int data;   // 노드의 번호
    ArrayList<Node> adjacents;   // 인접한 노드들
    boolean visited;   // 방문 여부

    Node(int data) {
        this.data = data;
        this.adjacents = new ArrayList<>();
        this.visited = false;
    }
}

그래프를 구성하는 각 노드에 대한 정보를 정의한 클래스이다. 각 노드는 "노드의 번호", "인접한 노드들", "방문 여부"에 대한 정보를 가지고 있다.

 

/* 그래프 내의 노드를 연결하는 메서드 */
void addEdge(int index01, int index02) {
    if (!nodes[index01].adjacents.contains(nodes[index02]))
        nodes[index01].adjacents.add(nodes[index02]);

    if (!nodes[index02].adjacents.contains(nodes[index01]))
        nodes[index02].adjacents.add(nodes[index01]);
}

그래프 내의 노드들을 연결하는 메서드이다. 연결된 두 대의 컴퓨터에 대한 정보를 매개변수로 입력받아 서로의 인접 노드로 추가한다.

 

/* 그래프 내의 존재하는 네트워크를 탐색 */
int bfs(int startNode) {

    /* 이미 방문한 노드인 경우 0 반환 */
    if (nodes[startNode].visited == true)
        return 0;

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

    nodes[startNode].visited = true;

    queue.add(nodes[startNode]);

    while (!queue.isEmpty()) {
        Node node = queue.poll();

        for (Node next : node.adjacents) {
            if (next.visited == false) {
                next.visited = true;
                queue.add(next);
            }
        }
    }

    /* 그렇지 않은 경우 1 반환 */
    return 1;
}

BFS 알고리즘을 이용해서 그래프 내의 존재하는 네트워크를 탐색한다.

 

전체 소스코드

import java.io.*;
import java.util.*;

public class Solution01 {
	public int solution(int n, int[][] computers) {

		Graph graph = new Graph(n);

		for (int i = 0; i < computers.length; i++) {
			for (int j = 0; j < computers[i].length; j++) {
				/* 두 대의 컴퓨터가 서로 연결되어 있는 경우 */
				if (computers[i][j] == 1 && i != j) {
					int index01 = i;
					int index02 = j;

					graph.addEdge(index01, index02);
				}

			}
		}

		int answer = 0;

		for (int i = 0; i < n; i++) {
			answer += graph.bfs(i);
		}

		return answer;
	}

	/** 그래프에 대한 정보를 정의 */
	static class Graph {
		/* 그래프의 각 노드에 대한 정보를 정의 */
		class Node {
			int data;
			ArrayList<Node> adjacents;
			boolean visited;

			Node(int data) {
				this.data = data;
				this.adjacents = new ArrayList<>();
				this.visited = false;
			}
		}

		Node[] nodes;

		/* 그래프 생성자 */
		Graph(int size) {
			nodes = new Node[size];

			for (int i = 0; i < size; i++) {
				nodes[i] = new Node(i);
			}
		}

		/* 그래프 내의 노드를 연결하는 메서드 */
		void addEdge(int index01, int index02) {
			if (!nodes[index01].adjacents.contains(nodes[index02]))
				nodes[index01].adjacents.add(nodes[index02]);

			if (!nodes[index02].adjacents.contains(nodes[index01]))
				nodes[index02].adjacents.add(nodes[index01]);
		}

		/* 그래프 내의 존재하는 네트워크를 탐색 */
		int bfs(int startNode) {

			/* 이미 방문한 노드인 경우 0 반환 */
			if (nodes[startNode].visited == true)
				return 0;

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

			nodes[startNode].visited = true;

			queue.add(nodes[startNode]);

			while (!queue.isEmpty()) {
				Node node = queue.poll();

				for (Node next : node.adjacents) {
					if (next.visited == false) {
						next.visited = true;
						queue.add(next);
					}
				}
			}

			/* 그렇지 않은 경우 1 반환 */
			return 1;
		}

	}
}

 

DFS를 이용한 풀이

import java.io.*;
import java.util.*;

public class Solution01 {
	static boolean[] visited; // 각 컴퓨터의 탐색 여부를 확인하는 배열

	public int solution(int n, int[][] computers) {

		visited = new boolean[n];

		int answer = 0;

		for (int i = 0; i < n; i++) {
			if (visited[i] == false) {
				answer++;
				dfs(i, computers);
			}
		}

		return answer;
	}

	/** dfs를 이용하여 네트워크를 탐색하는 메서드 */
	static void dfs(int current, int[][] computers) {
		visited[current] = true; // 방문한 컴퓨터는 true로 변경

		for (int i = 0; i < computers.length; i++) {
			/* 현재 탐색중인 컴퓨터와 네트워크를 이루고 있는 경우 */
			if (computers[i][current] == 1 && visited[i] == false) {
				dfs(i, computers);
			}
		}
	}
}

기존의 풀이 방식은 연결된 컴퓨터의 정보를 이용해 그래프를 구성하고, 구성된 그래프를 통해 몇 개의 네트워크가 존재하는지 계산하는 방식이었다.

하지만, 컴퓨터의 방문 여부를 확인하는 배열을 하나 선언한 후, 재귀적으로 컴퓨터의 방문 여부를 계속 갱신시킴으로써 더욱 쉽게 문제를 해결할 수 있다.