[프로그래머스][Java] lv3 네트워크 (DFS) - 문제풀이 및 팁

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

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

 

문제요약

여러 컴퓨터끼리 네트워크로 연결된 정보(간선)가 인접행렬로 주어질때,

해당 인접행렬에 몇개의 네트워크(그래프)가 존재하는지를 구하는 문제.

 

풀이

1. 각 컴퓨터(노드)를 순서대로 dfs 탐색 (=해당 노드가 포함된 그래프를 탐색하며 그래프에 속한 노드를 체크)

- 첫번째 컴퓨터의 dfs 탐색이 끝나면, 첫번째 컴퓨터와 같은 그래프에 포함된 컴퓨터들은 이미 모두 체크되어있음.(소스코드 참고)

- 다음 컴퓨터가 체크가 안되있으면, 다른 그래프에 포함된 컴퓨터임을 의미함(=새로운 네트워크이므로 카운트 증가).

  해당 컴퓨터부터 dfs 탐색을 수행하여 포함된 컴퓨터들을 모두 체크

- 반복~~~

 

2. dfs

같은 네트워크(그래프)를 탐색하며 포함된 컴퓨터 모두 체크

---

방문한 컴퓨터를 체크하는 배열의 참조변수를 dfs의 재귀 호출시 넘겨주어 체크했음.

(static으로 선언하고 dfs 메서드에서 접근하도록 하는 것도 가능)

 

소스코드

https://github.com/999inim/Algorithm/blob/main/programmers/PS47.java

---

API 정리 및 팁

 

1. 배열 같은 값으로 초기화 하기

import java.util.Arrays;

boolean[] checked = new boolean[n]; 
Arrays.fill(checked, true);

boolean 값은 false로 초기화되기 때문에 이번 문제에서는 따로 초기화할 필요없었음

 

 

2. 2차원 행렬 다루기

row가 고정된 상태에서 col 순회하기

 for(int col = 0; col < len; col++) {
    if(arr2[current][col]==1 && !checked[col]) {
    	dfs(col, arr2, checked);
    }            
}

 

 

---

느낀점

1. 유형(dfs)임을 미리 알아서 접근방식에 끼워맞추려는 시도↓

그래프 1개에 대한 인접행렬을 주고 탐색하면서 원하는 답을 계산하고 캐시하거나 반환하는 문제가 아님.

구하고자 하는 답을 확인하고, 그 답을 찾기위한 접근방법을 찾을 것.

 

2. 흐름도를 생각하기 (무지성 코드구현 지양)

문제 풀이 시작할때 개략적인 흐름도를 예상하고,

구현할때는 현재 위치가 흐름도상 어디쯤에 위치하는지 인지하면서 코드작성하기.

 

3. 재귀, stack, bfs, 인접리스트

이후에 다양한 방법으로 풀어보고 차이점 확인하기.