.png&blockId=18f00b21-a9bc-4e35-aeb8-ecb07bddb89a)
알고리즘 설명
DFS란?
Depth-First Search = 깊이 우선 탐색 깊은 부분을 우선적으로 탐색하는 알고리즘 그래프의 완전 탐색에 많이 사용되는 알고리즘 재귀를 사용하여 구현하거나 Stack을 사용하여 구현 시간 복잡도 = O (V+E) V : 노드 수, E : 에지 수 실제 구현 시 재귀 함수를 이용하므로 스택오버플로우(StackOverFlow)에 주의해야 함BFS란?
Breath-First Search = 너비 우선 탐색 그래프에서 부모 노드를 먼저 방문한 후, 방문했던 부모 노드의 자식 노드를 차례로 탐색하는 알고리즘 그래프 탐색 알고리즘 중 1개 Queue를 사용하여 구현 시간 복잡도 = O (V+E) V : 노드 수, E : 에지 수DFS와 BFS를 위한 백준 문제 추천 DFS와 BFS
오늘의 알고리즘 문제
네트워크
접근방법
모든 그래프(컴퓨터 연결)을 돌아보며 연결이 되어 있는지 확인해야 함 모든 경우의 수를 탐색할 수 있는 DFS로 풀어보자 소스 코드
public class Solution{ // 네트워크
public static void main(String[] args) {
int n = 3;
int[][] computers = { { 1, 1, 0 }, { 1, 1, 0 }, { 0, 0, 1 } };
// int n = 3;
// int[][] computers = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
System.out.println(solution(n, computers));
}
private static int solution(int n, int[][] computers) {
int answer = 0;
boolean[] v = new boolean[n];
for (int i = 0; i < computers.length; i++) {
if(!v[i]) {
v = dfs(computers, v, i);
answer++;
}
}
return answer;
}
private static boolean[] dfs(int[][] computers, boolean[] v, int computer) {
v[computer] = true;
for (int i = 0; i < computers.length; i++) {
if(computers[computer][i] == 1 && !v[i]) {
dfs(computers, v, i);
}
}
return v;
}
}
Java
복사
실행 결과
타겟넘버
접근 방법
덧셈, 뺄셈의 모든 경우를 생각해보아야 함 모든 경우의 수를 탐색할 수 있는 DFS로 풀어보자 소스 코드
public class Solution { // 타겟 넘버
static int cnt = 0;
public static void main(String[] args) {
// int[] numbers = {1, 1, 1, 1, 1};
// int target = 3;
int[] numbers = {4, 1, 2, 1};
int target = 4;
System.out.println(solution(numbers, target));
}
private static int solution(int[] numbers, int target) {
dfs(numbers, target, 0, 0); // 배열, 만들 숫자, 인덱스, sum
return cnt;
}
private static void dfs(int[] numbers, int target, int idx, int sum) {
// 기저 조건
if(idx == numbers.length) { // 다 골랐다
if(sum == target) {
cnt++;
}
} else {
dfs(numbers, target, idx + 1, sum+numbers[idx]); // 더해보기
dfs(numbers, target, idx + 1, sum-numbers[idx]); // 빼보기
}
}
}
Java
복사
실행 결과
Refactor
public class Solution { // 타겟 넘버
// static int cnt = 0;
public static void main(String[] args) {
// int[] numbers = {1, 1, 1, 1, 1};
// int target = 3;
int[] numbers = {4, 1, 2, 1};
int target = 4;
System.out.println(solution(numbers, target));
}
private static int solution(int[] numbers, int target) {
return dfs(numbers, target, 0, 0);
}
private static int dfs(int[] numbers, int target, int idx, int sum) {
// 기저 조건
if(idx == numbers.length) { // 다 골랐다
if(sum == target) {
return 1;
}
return 0;
}
return dfs(numbers, target, idx + 1, sum+numbers[idx]) + dfs(numbers, target, idx + 1, sum-numbers[idx]);
}
}
Java
복사
