Hyemi Lee

Hyemi Lee

주니어 개발자의 삽질과 기록

Algorithm, programmers, 네트워크(43162)

풀이

  • 0부터 n까지의 노드를 차례로 깊이우선으로 탐색한다.
  • 탐색한 노드는 visited를 이용하여 true로 변경해준다.
  • 탐색이 완료된 노드의 다음 노드를 방문했는지 visited로 확인하고, 방문하지 않았다면 해당 노드를 깊이우선으로 탐색한다.
  • 깊이 우선으로 탐색할때 마다 network 는 +1 해준다.

package org.programmers;
public class Level3_network_43162 {
	public static void main(String[] args) {
		int[][] c = { {1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
		int[][] c2 = {	{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
		solution(3, c);
	}
	public static int solution(int n, int[][] computers) {
		int answer = 0;
		boolean[][] visited = new boolean[n][n];
		for(int i=0; i<computers.length; i++) {
			// 해당노드를 방문하지 않았다면, 해당노드의 네트워크를 모두 방문한 후에 +1
			if(visited[i][i] == false) {
				findWay(i, computers, visited);
				answer++;
			}
		}
		return answer;
	}
	// index노드와 인접한 모든 노드를 방문합니다
	public static void findWay(int index, int[][] computers, boolean[][] visited) {
		for(int j=0; j<computers.length; j++) { 			
			if( visited[index][j] == false && computers[index][j] == 1) {			
				visited[index][j] = visited[j][index] = true;
				findWay(j, computers, visited);
			}		
		} 			
	}
}

Reference

Share on

Twitter Facebook LinkedIn

You may also enjoy

Redis Stream

2021年04月28日

Stream Stream은 로그 데이터를 처리하게위해 5.0에서 새로 도입된 데이터 타입입니다. 대량의 데이터가 연속적으로 발생할때 처리하기 위해 등장했습니다. 기존 데이터를 수정하지 않고 오직 추가로 발생합니다. 이런 종류의 데이터를 stream or log데이터...

Study, Object, chapter2&3 presentation

2021年04月20日

chapter03. 역할, 책임, 협력 객체지향 설계란, 올바른 객체에게 올바른 책임을 할당하면서 낮은 결합도와 높은 응집도를 가진 구조를 창조하는 활동이다.

Spring, chatting 프로그램 만들기, Reactive란?

2020年06月16日

Reactive 막힘없이 흘러다니는 data(event)를 통해 사용자에게 자연스러운 응답을 주고 규모 탄력적으로 리소스를 사용하며 실패에 있어서 유연하게 대처한다 모든 지점에서 블럭 되지 않게 하자 oop와 같은 패러다임 모든 것을 비동기적인 data의 strea...