코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS)

level 2. 타겟 넘버

class Solution {
	static int ans = 0;

	public int DFS(int L, int[] numbers, int n, int target) {
        
		if (L == numbers.length) {
			if (n == target)
				ans++;
		} else {
			DFS(L + 1, numbers, n + numbers[L], target);
			DFS(L + 1, numbers, n - numbers[L], target);
		}
		return ans;
	}

	public int solution(int[] numbers, int target) {
		int answer = 0;
		answer = DFS(0, numbers, 0, target);
		return answer;
	}
}

 

level 2. 네트워크

class Solution {
	static int[] check;
	static int[][] board;

	public void DFS(int v, int n) {
		check[v] = 1;
		for (int i = 0; i < n; i++) {
			if (board[v][i] == 1) {
				board[v][i] = 0;
				DFS(i, n);
			}
		}
	}

	public int solution(int n, int[][] computers) {
		int answer = 0;
		board = computers;
		check = new int[n];
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (board[i][j] == 1) {
					check[i] = 1;
					board[i][j] = 0;
					answer++;
					// DFS으로 연결된 컴퓨터들 제외
					DFS(j, n);
				}
			}
		}
		for (int i = 0; i < n; i++)
			if (check[i] == 0)
				answer++;
		return answer;
	}
}

 

level 3. 단어 변환

class Solution {
	static int answer;
	static int[] ch;
	static String Target;
	static String[] Words;

	public boolean comp(String cur_word, String comp_word) {
		int cnt = 0;
		for (int i = 0; i < cur_word.length(); i++) {
			if (cur_word.charAt(i) != comp_word.charAt(i))
				cnt++;
			if (cnt > 1)
				return false;
		}
		return true;
	}

	public void DFS(int L, String word) {
		if (word.equals(Target)) {
			answer = Math.min(answer, L);
		} else if (L == Words.length) {
			return;
		} else {
			for (int i = 0; i < Words.length; i++) {
				if (ch[i] != 1 && comp(word, Words[i])) {
					ch[i] = 1;
					DFS(L + 1, Words[i]);
					ch[i] = 0;
				}
			}
		}
	}

	public int solution(String begin, String target, String[] words) {
		answer = Integer.MAX_VALUE;
		Target = target;
		Words = words;
		ch = new int[words.length];
		DFS(0, begin);
		if (answer == Integer.MAX_VALUE)
			return 0;
		return answer;
	}
}

 

level 3. 여행경로

import java.util.*;

class Solution {
	public String[] solution(String[][] tickets) {
		String[] answer;

		Map<String, PriorityQueue<String>> map = new HashMap<>();
		for (int i = 0; i < tickets.length; i++) {
			map.put(tickets[i][0], map.getOrDefault(tickets[i][0], new PriorityQueue<String>()));
			map.get(tickets[i][0]).offer(tickets[i][1]);
		}

		String from = "ICN";
		ArrayList<String> arr = new ArrayList<>();
		arr.add(from);
		for (int i = 0; i < tickets.length; i++) {
			String to = map.get(from).poll();
			arr.add(to);
			from = to;
		}

		answer = new String[arr.size()];
		int i = 0;
		for (String str : arr)
			answer[i] = arr.get(i++);

		return answer;
	}
}

윗 코드는 문제를 잘못 이해해서 알파벳 순서대로 방문 하였을 때 경로가 없는 경우 런타임 에러(아마도 널포인터익셉션)가 발생했다.

import java.util.*;

class Ticket implements Comparable<Ticket> {
	String from, to;

	Ticket(String from, String to) {
		this.from = from;
		this.to = to;
	}

	@Override
	public int compareTo(Ticket o) {
		return this.to.compareTo(o.to);
	}

}

class Solution {
	static String[] temp;
	static String[] answer;
	static String[][] Tickets;
	static int[] ch;
	static ArrayList<Ticket> arr;
	static boolean flag = false;

	public void DFS(int L, String from) {
		if (!flag) {
			if (L == Tickets.length + 1) {
				if (!flag) {
					flag = true;
					int idx = 0;
					answer = new String[Tickets.length + 1];
					for (String str : temp) {
						answer[idx++] = str;
					}
				}
			} else {
				for (int i = 0; i < Tickets.length; i++) {
					if (ch[i] == 0 && arr.get(i).from.equals(from)) {
						ch[i] = 1;
						temp[L] = arr.get(i).to;
						DFS(L + 1, arr.get(i).to);
						ch[i] = 0;
					}
				}
			}
		}
	}

	public String[] solution(String[][] tickets) {
		temp = new String[tickets.length + 1];
		Tickets = tickets;
		ch = new int[tickets.length];
		arr = new ArrayList<>();
		for (int i = 0; i < tickets.length; i++) {
			arr.add(new Ticket(tickets[i][0], tickets[i][1]));
		}
		Collections.sort(arr);
		temp[0] = "ICN";
		DFS(1, "ICN");
		return answer;
	}
}

생각없는 static 남용 반성..

다음 부터는 입력 배열을 이름 같은 클래스 멤버 변수 생성해서 this로 받거나 그냥 주소를 파라미터로 넘겨줘야겠다..

 

 

문제 출처 : https://programmers.co.kr/learn/courses/30/parts/12421