문제https://www.acmicpc.net/problem/14244 풀이트리의 개념을 활용한 구현 문제입니다. 이 문제에서 리프란, 간선이 하나밖에 없는 노드입니다. 그래서 트리의 끝만 포함되는 것이 아니라, 조건이 맞다면 루트도 포함될 수 있습니다. 소스 코드의 주석으로 풀이를 대체하겠습니다. 소스 코드import java.util.Scanner;public class B14244_트리만들기 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int leafCount = 0..
BOJ
문제https://www.acmicpc.net/problem/17073 풀이트리 문제입니다. 처음 아이디어는 트리를 순회해야한다는 생각에 트리를 dfs로 순회하며 리프 노드와 깊이를 구했습니다. 그래서 2의 (깊이) 승을 w에 나누어W/(Math.pow(2, depth));와 같이 식을 구성했습니다.그런데 생각해보니, 수학에서 결합 법칙을 생각해보면, 모든 확률의 합은 1이기 때문에 기대 값은 W 그대로라는 것을 알 수 있습니다. 그래서 결과는 W / 리프 노드의 개수를 구한 값입니다. ArrayList에 입력을 받을 때 양방향 간선 트리에서 리프노드의 연결 값의 size는 1이라는 쉬운 특징이 있었습니다. 이를 통해 리프노드의 개수를 세어주었습니다. 추가로, 이 문제에서 부모 노드가 자식 노드보다..
문제https://www.acmicpc.net/problem/2661 풀이백트래킹을 활용한 문제입니다. 처음에 문제를 보고 정말 많이 헤맸는데, 숫자형으로 표현해야한다는 무의식적인? 고집이 있었습니다. 수열이다보니 숫자로 어떻게 조합을 잘 해야겠다라고 생각한 것이 시간을 많이 잡아먹었습니다. 이 문제에서 포인트가 두 가지가 있다고 생각합니다. 첫 번째는 나타낼 수열을 String으로 받는 것, 그리고 좋은 수열인지 아닌지를 어떻게 판단할지입니다. 전체적인 구조는 백트래킹 메서드의 매개변수를 String 형의 수열로 받아, 좋은 수열이 맞다면 다시 재귀를 돌려주는 방식입니다. 좋은 수열인지를 판단하는 메서드는 String을 subString으로 나누어 반복문을 돌며 구간 검사를 진행하면 됩니..
문제https://www.acmicpc.net/problem/1063 풀이 구현 문제입니다. 입력값을 어떤 형식으로 받을 것인지, 그리고 구현을 위한 메서드를 어떻게 나누고 적용할 것인지가 중요한 포인트 같습니다. 처음 구현시에 입력값도 String으로 받고 메서드를 제대로 분리하지 못했더니 너무 코드가 난잡해져서, 다시 입력 자료구조와 메서드를 정의해 문제를 해결했습니다. 우선 입력 시 char[] 배열을 통해 체스의 행과 열을 각각의 인덱스에 저장을 해주었습니다. 메서드는 크게 두 가지인데, chess를 옮기는 것과 범위를 체크하는 것입니다. 이 메서드를 king과 stone을 옮길 때 모두 사용할 수 있게끔 유연하게 만들어주었습니다. 그리고 조건에 통과해야지만, 이동된 배열 값에 업데이트를..
문제https://www.acmicpc.net/problem/18223 풀이다익스트라를 활용한 문제입니다. 일반적인 다익스트라 문제와 다른 것은, 특정한 경로를 지나칠 때를 고려해야한다는 것입니다. 특정한 경로를 지나치게하기 위해서 어떤 특별한 장치를 해야하는 것은 아니고, 그 특정 지점에서 다익스트라 알고리즘을 통해 각각의 노드까지의 최단 거리를 구해주기만 하면 됩니다. 그리고 그렇게 구한 최단 거리 배열을 통해 정답을 구할 수 있습니다. 아래는 소스 코드입니다. 소스 코드import java.util.ArrayList;import java.util.Arrays;import java.util.PriorityQueue;import java.util.Scanner;public class B1822..
문제https://www.acmicpc.net/problem/15681 풀이 서브 트리에 속한 정점의 개수를 세는 문제입니다. dfs를 통해 그래프를 탐색하며, 서브 트리의 루트가 인덱스인 배열에 정점의 개수를 저장합니다. 처음에 문제를 풀이할 때, 루트가 아닌 제일 마지막 자식부터 dfs 탐색을 시작해보려고도 했지만, 그렇게 접근하면 마지막 자식도 체크해야하고, 방문 배열을 통해 접근을 막아주어야하고.. 여러모로 로직이 복잡해집니다. 그래서 루트부터 출발해 자식으로 뻗어가며 subtrees 배열에 정점의 개수를 저장합니다. 이때 부모 노드에 자식 노드가 가진 정점의 개수를 더해주면 됩니다. 주의할 것은, 부모에서 자식으로 내려갔는데 다시 부모 노드를 검사하지 않도록 하는 것입니다. 이것은 d..
