네트워크 (level 3)

이번문제는 dfs/bfs로 풀 수 있는 문제입니다.

 

처음에는 이차원 배열을 활용한 dfs로 구현하였으나, 단방향/양방향에 이슈로 인해 정답이 제대로 나오지 않았습니다.

 

처음에 구현한 방식은 이차원 배열의 값들을 하나씩 체크하여, 지나갈 수 있고 방문가능한 갯수를 세었습니다.

 

[1, 0, 0, 1]

[0, 1, 1, 0]

[0, 1, 1, 0]

[1, 1, 0, 1]]

이렇게 하다보니 위와 같은 케이스에서 단방향/양방향 이슈에 직면하였습니다. (2->4 = 0)

 

물론 이것을 양방향으로 만들어도 원하는 결과를 도출해 낼 수 없었습니다. 

그 이유는 원하는 정답을 도출해 내는 방식이 틀렸기 때문이라고 생각합니다. 

 

그리하여, 리스트를 활용한 dfs를 활용했습니다. 

 

네트워크와 같이 하나의 흐름을 쭉 확인해야하는 문제는, 이차원 배열을 이용한 체크말고,

연결리스트나 visited를 일차원 배열로 갖는 방식을 사용해야합니다. 이 부분이 가장 핵심이라고 생각합니다.

import java.util*;

class Solution {

	public boolean[] visited;

	public int solution(int n, int[][] computers) {
		int answer = 0;

		visited = new boolean[n]; // 초기화

		List<List<Integer>> list = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			list.add(new ArrayList<>());
		}

		// 연결리스트 세팅
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (computers[i][j] == 1 && i != j) {
					list.get(i).add(j);
				}
			}
		}

		for (int i = 0; i < n; i++) {
			if (visited[i] == false) { // 방문안한 노드만 실행
				dfs(i, list);
				answer++;
			}
		}

		return answer;
	}

	public void dfs(int x, List<List<Integer>> list) {
		visited[x] = true;

		List<Integer> alist = list.get(x); //연결된 다음 노드로 이동
		for (Integer a : alist) {
			if (visited[a] == false) {
				dfs(a, list);
			}
		}
	}
}