09-06. DFS(깊이 우선 탐색)
0. 문제 유형
모든 경로 탐색
1. 네트워크
프로그래머스 Lv.3 / 체감 난이도 Lv.2
끝까지 가는 모든 경로를 탐색하는 문제
import java.util.*;
class Solution {
public int solution(int n, int[][] computers) {
int answer = 0;
boolean[] check = new boolean[n];
for (int i = 0; i < n; i++) {
if(!check[i]) {
dfs(computers, i, check);
answer++;
}
}
return answer;
}
public void dfs(int[][] computers, int i, boolean[] check) {
check[i] = true;
for(int j = 0; j < computers.length; j++) {
if (i != j && computers[i][j] == 1 && !check[j]) {
dfs(computers, j, check);
}
}
}
}2. 단어 변환
프로그래머스 Lv.3 / 체감 난이도 Lv.3
하나씩 끝까지 만들어보면서 단어를 찾음 + 이미 사용한 단어 체크하는 배열
import java.util.*;
class Solution {
static boolean[] visited;
static int answer;
public int solution(String begin, String target, String[] words) {
visited = new boolean[words.length];
dfs(begin, target, words, 0);
return answer;
}
public static void dfs(String begin, String target, String[] words, int cnt) {
if (begin.equals(target)) {
answer = cnt;
return;
}
for (int i =0; i < words.length; i++) {
if (visited[i]) {
continue;
}
int k = 0;
for (int j = 0; j < begin.length(); j++) {
if (begin.charAt(j) == words[i].charAt(j)) {
k++;
}
}
if (k == begin.length() - 1) {
visited[i] = true;
dfs(words[i], target, words, cnt+1);
visited[i] = false;
}
}
}
}3. 여행 경로
프로그래머스 Lv.3 / 체감 난이도 Lv.3
끝까지 가는 모든 경로를 탐색하는 문제 + 정렬
import java.util.*;
class Solution {
static List<String> answer;
static boolean[] visited;
public String[] solution(String[][] tickets) {
answer = null;
visited = new boolean[tickets.length];
// 출발지가 같은 경우 도착지를 기준으로 정렬
Arrays.sort(tickets, (a, b) -> {
if(a[0].equals(b[0])) {
return a[1].compareTo(b[1]);
}
return a[0].compareTo(b[0]);
});
List<String> route = new ArrayList<>();
route.add("ICN");
dfs(tickets, "ICN", route, 0);
return answer.toArray(new String[0]);
}
public void dfs(String[][] tickets, String current, List<String> route, int count) {
if(count == tickets.length) {
// 처음 찾은 경로이거나 더 알파벳 순서가 앞선 경로를 찾은 경우
if(answer == null) {
answer = new ArrayList<>(route);
}
return;
}
for(int i = 0; i < tickets.length; i++) {
if(!visited[i] && tickets[i][0].equals(current)) {
visited[i] = true;
route.add(tickets[i][1]);
dfs(tickets, tickets[i][1], route, count + 1);
// 백트래킹
route.remove(route.size() - 1);
visited[i] = false;
}
}
}
}4. 불량사용자
프로그래머스 Lv.3 / 체감 난이도 Lv.3
DFS + 백 트래킹
import java.util.*;
class Solution {
private HashSet<HashSet<String>> result; // 최종 결과를 저장할 Set
public int solution(String[] user_id, String[] banned_id) {
result = new HashSet<>();
// 각 불량 사용자 패턴별로 매칭되는 사용자 ID를 저장
List<List<String>> matchList = new ArrayList<>();
// 각 불량 사용자 패턴에 매칭되는 사용자 ID들을 찾음
for(String banned: banned_id) {
List<String> matches = new ArrayList<>();
for(String user: user_id) {
if(match(user, banned)) {
matches.add(user);
}
}
matchList.add(matches);
}
// DFS로 가능한 모든 조합을 찾음
dfs(new HashSet<>(), 0, matchList);
return result.size();
}
private void dfs(HashSet<String> set, int depth, List<List<String>> matchList) {
// 모든 불량 사용자를 처리했으면 결과에 추가
if(depth == matchList.size()) {
result.add(new HashSet<>(set));
return;
}
// 현재 불량 사용자에 매칭되는 사용자 ID들에 대해 반복
for(String user: matchList.get(depth)) {
// 이미 선택된 사용자 ID는 건너뜀
if(!set.contains(user)) {
set.add(user);
dfs(set, depth + 1, matchList);
set.remove(user);
}
}
}
private boolean match(String user, String banned) {
if(user.length() != banned.length()) {
return false;
}
for(int i = 0; i < user.length(); i++) {
if(banned.charAt(i) != '*' && banned.charAt(i) != user.charAt(i)) {
return false;
}
}
return true;
}
}5. 다단계 칫솔 판매
프로그래머스 Lv.3 / 체감 난이도 Lv.3
트리구조지만 Map과 DFS로 풀 수 있는 문제
import java.util.*;
class Solution {
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
// map
Map<String, Integer> profitMap = new HashMap<>();
Map<String, String> referralMap = new HashMap<>();
for(int i = 0; i < enroll.length; i++) {
profitMap.put(enroll[i], 0); // 0원 으로 초기화
referralMap.put(enroll[i], referral[i]);
}
for(int i = 0; i < seller.length; i++) {
dfs(profitMap, referralMap, seller[i], amount[i]*100);
}
int[] answer = new int[enroll.length];
for(int i = 0; i < enroll.length; i++) {
answer[i] = profitMap.get(enroll[i]);
}
return answer;
}
public void dfs(Map<String, Integer> profitMap, Map<String, String> referralMap, String name, int profit) {
if (profit < 10) {
profitMap.put(name, profitMap.get(name) + profit);
} else {
int ownProfit = (profit * 9 + 9) / 10; // 올림 처리된 자신의 몫
int referralProfit = profit / 10; // 추천인의 몫
profitMap.put(name, profitMap.get(name) + ownProfit);
if (!referralMap.get(name).equals("-")) {
dfs(profitMap, referralMap, referralMap.get(name), referralProfit);
}
}
}
}Last updated