mondegreen

재귀..재귀..진짜 왜 재귀적 머리가 안 돌아가는지.. 한참 고민하고 푼 문제이다. 일단 타겟을 찾는 것보다 어쨋든 답이 나오는 문제라면 빼주어야 하는 값을 찾기로 한다. 오래 걸린 부분은 현재 이 숫자를 선택하느냐 마느냐라는 부분을 어떤 방식으로 구현하는 것인지였다. 아래와 같이 선택 여부에 따라 dfs를 나누어 실행해주고 만약 더한 값이 찾고자 하는 값보다 크면 바로 return해 버리는 방식으로 구현했다. class Solution { private static int find, answer; public int solution(int[] numbers, int target) { answer = 0; int total = 0; for(int i =0; i find) return; if(thisNum..

그래프 너무 어렵지만.. 가중치가 없는 그래프이니까 다익스트라 제외, 최단경로가 아니라 어디까지 이어져 있는지가 중요하니까 BFS가 아닌 DFS로 구현하기로 결정했다. 보통은 두개의 트리로 분리되어 있는 송전탑을 하나의 트리로 연결시키라고 하면 너무...정말... 유니온파인드 써서 쉽게 처리하겠지만 이건 반대로 한개를 두개로 나누라고 하니 풀이방법을 찾지 못했다. 아래는 책을 참고해서 푼 로직이다. 답인 answer는 최대값인 n-1로 설정한다. 그 이유는 다른 한쪽이 한 개의 송전탑으로 이루어진 경우에 가장 큰 차이를 가지는 때이므로 n-1로 초기화해준다. DFS부분이 문제인데 송전탑을 하나씩 연결해가면서 나머지 송전탑 무리들과의 차이를 최솟값으로 갱신해나간다. 그래서 현재 송전탑이 연결된 것으로 가정..

import java.util.*; class Solution { public static Deque dq; public static int dist[][]; public static int n, m; public static class Position{ int r; int c; public Position(int x, int y){ this.r = x; this.c = y; } } public int solution(int[][] maps) { int answer = -1; n = maps.length; m = maps[0].length; dist = new int[n][m]; dist[0][0] = 1; dq = new ArrayDeque(); dq.add(new Position(0, 0)); int..