[Programmers 프로그래머스] 43162 네트워크 (JAVA)

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

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

 

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.

입출력 예

 

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

 

 

이 문제를 해결하기 위해 Point 라는 클래스를 따로 만들어서 좌표값을 저장할 수 있도록 했습니다.

그렇게 만들어진 Point를 활용을 해서 리스트에 computers에서 1인 것을 담아주고, while문을 통해 연결된 모든 1을 0으로 만들어 줍니다.

그렇게 0으로 모두 만들면서 while문이 돌아간 횟수를 바탕으로 답을 계산해 줍니다.

import java.util.LinkedList;

class Solution {
   class Point {	//좌표 저장해 주는 배열
		int x, y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

	}
    public int solution(int n, int[][] computers) {
		int answer = 0;
		LinkedList<Point> que = new LinkedList<>();
		while (check(computers)) {
			outer:
			for (int i = 0; i < computers.length; i++) {	//1인 곳 하나를 리스트에 저장
				for (int j = 0; j < computers[0].length; j++) {
					if (computers[i][j] == 1) {
						que.add(new Point(i, j));
						computers[i][j] = 0;
						break outer;
					}
				}
			}

			while (!que.isEmpty()) {	//네트워크가 연결된 모든 값을 0으로
				Point p = que.poll();
				for (int i = 0; i < computers.length; i++) {
					if (computers[p.y][i] == 1) {
						computers[p.y][i] = 0;
						que.add(new Point(p.y, i));
					}
				}
			}
			answer++;
		}
		return answer;
    }
    public boolean check(int[][] computers) {	//배열에 1이 남아있는지 확인
		for (int i = 0; i < computers.length; i++) {
			for (int j = 0; j < computers[0].length; j++) {
				if (computers[i][j] == 1) {
					return true;
				}
			}
		}
		return false;
	}
}