성능 요약
- 메모리: 71.4 MB, 시간: 0.10 ms
구분
- 코딩테스트 연습 > 깊이/너비 우선 탐색 > 네트워크
Answer Code1(23.11.08)
class Solution {
public int solution(int n, int[][] computers) {
int answer = 0;
boolean[] visited = new boolean[computers.length];
// 노드 방문 초기화
for (boolean visit : visited) {
visit = false;
}
for(int i = 0; i < computers.length; i++) {
if(visited[i] == false) { // 해당 노드를 방문하지 않았을 경우
answer++; // 새로운 네트워크 찾았으므로 +1 증가
dfs(i, visited, computers);
}
}
return answer;
}
// node: 현재 노드, visited: 방문여부, computers: 컴퓨터간의 연결 정보를 나타내는 2차원 배열
public void dfs(int node, boolean[] visited, int[][] computers) {
visited[node] = true;
for(int i = 0; i < computers.length; i++) {
// 아직 방문하지 않는 노드 && 현재 노드와 연결된 경우
if(visited[i] == false & computers[node][i] == 1) {
dfs(i, visited, computers);
}
}
}
}
문제풀이(Answer Code1)
DFS에 대한 알고리즘 개념을 안 상태로 해당 문제에 접근하면,
(1) 처음에 노드 방문을 boolean 배열을 만들어서 컴퓨터의 개수(n)만큼 for문을 돌려서 초기화해주고,
(2) visited[i] 값이 false이면 깊이 우선 탐색(dfs) 메서드를 호출하고 answer++ 해준다.
(3) 전달받은 파라미터인 visited[i] 값을 true로 바꿔준다.
(4) computers[] 길이만큼 반복문들 돌면서
(5) 아래 조건을 모두 만족하면 재귀 호출을 한다.
-
자기 자신이 아니며 (i != j)
-
visited 배열 i의 위치 값이 false이며
-
computers 배열의 값이 1인 것
(6) 2번으로 돌아간다.
(7) answer을 리턴한다.
Answer Code2(23.12.14)
// 프로그래머스 - 네트워크
class Solution {
static boolean[] visited;
public int solution(int n, int[][] computers) {
int answer = 0;
visited = new boolean[computers.length];
// 노드 방문 초기화
for(boolean visit : visited) {
visit = false;
}
for(int i = 0; i < computers.length; i++) {
if(visited[i] == false) {
answer ++;
dfs(i, computers);
}
}
return answer;
}
/*
* node: 현재 노드
* visited: 방문여부
* computer: 컴퓨터간의 연결 정보를 나타내는 2차원 배열
*/
public void dfs(int node, int[][] computers) {
visited[node] = true;
for(int i = 0; i < computers.length; i++) {
if(visited[i] == false && computers[node][i] == 1) {
dfs(i, computers);
}
}
}
}
Review(23.12.14)
-
첫번째 풀이와 다른 점은 visited 배열을 static으로 선언해서 dfs를 호출할 때, visited 매개변수를 없애주었다.
-
해당 문제는
연결된 요소 찾기유형과 흡사해서, 이전에 풀었던 문제와 비슷했지만, 아직은 익숙치 않아서 더 자주 풀어봐야겠다.
Reference
- https://beaniejoy.tistory.com/41