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

📝문제 링크

프로그래머스 > 깊이/너비 우선 탐색 > 네트워크 문제보기

🔑문제 KeyPoint

DFS와 BFS의 개념을 확실히 이해하자.
이전에 작성한 글 중에 DFS vs BFS 문제로 이해하기를 참고하면, 해당 문제를 응용하여 풀 수 있다.

DFS는 인접행렬로 재귀적으로 호출하여 문제풀이
BFS는 큐를 이용한 문제풀이

문제를 풀면서 2가지 궁금증이 생겼다. ( 문제를 풀고 보니, 이런 궁금증때메 삽질을 했던 것 같다.)

• computers[i][i] 자기 자신은 무조건 1이면서, 굳이 신경쓰지 않아도 되는 값은 어떻게 처리를 할까?
  - 어차피 모든 정점의 방문여부를 체크할거라면, 신경쓰지 않아도 되는 부분이다.

• 네트워크의 개수를 언제 카운팅해줘야하는지?
  - 정점의 개수와 간선의 개수를 카운팅해야하나,, 연결이 되있을때마다 카운팅을 해주면 답이 안 맞았다. 결국 , 구팀장의 찬스를 이용해 해당 블로그를 보고 답을 찾았다.

그래서 해당 문제는
1. computers[i][j] = 1인 값이면서, 방문하지 않은 정점을 탐색하면 된다. (1<= i , j <= n)
2. i행의 모든 열을 돌았을 경우, 네트워크의 수는 +1 증가해준다.

💻문제 풀이

인접행렬을 이용하여 재귀호출 DFS 풀이

static boolean[][] visited;

public static int solution_dfs(int n, int[][] computers) {
	if(n==1) {return 1;}

	int answer=0;
	visited = new boolean[n][n];

	for(int i=0;i<n;i++) {
		// 시작점은 (0,0) ... (n,n)
		if(!visited[i][i]) {
			dfs(computers, i);
			answer++;		// 한번 호출하는 경우, 네트워크수 +1 증가한다고 봐야함.
						// 왜냐하면, 다 연결되어 있다면 , for문이 더 이상 반복되지 않기 때문	
		}
	}

	return answer;
}

public static void dfs(int[][] computers, int s) {
	int len = computers.length;

	for(int i=0;i<len;i++) {
		if(computers[s][i] == 1 && !visited[s][i] ){
			visited[s][i]=visited[i][s]=true;
			dfs(computers, i);
		}
	}
}

Queue을 이용한 BFS 풀이

static boolean visited_bfs[];		

public static int solution_bfs(int n, int[][] computers) {
	if(n==1) {return 1;}
	
	int answer=0;
	visited_bfs = new boolean[n];
	
	for(int i=0;i<n;i++) {
		// 시작점은 (0,0) ... (n,n)
		if(!visited_bfs[i]) {
			bfs(computers, i);
			answer++;			// 한번 호출하는 경우, 네트워크수 +1 증가한다고 봐야함.
			// 왜냐하면, 다 연결되어 있다면 , for문이 더 이상 반복되지 않기 때문	
		}
	}
	return answer;
}
public static void bfs(int[][] computers, int s) {
	int len = computers.length;
	
	Queue<Integer> q = new LinkedList<Integer>();
	q.offer(s);
	visited_bfs[s] = true;
	
	while(!q.isEmpty()) {
		int v = q.poll();
		
		for(int i=0;i<len;i++) {
			if(computers[v][i] ==1 && !visited_bfs[i]) {
				q.offer(i);
				visited_bfs[i] = true;
			}
		}
	}
	
}

전체 소스 보기