문제https://www.acmicpc.net/problem/15681 풀이주어진 간선을 바탕으로 무방향 그래프를 구성하고루트부터 재귀를 돌면서 해당 노드가 루트였을 때 서비 트리의 개수를 파악하는 문제입니다. 재귀에서 사용하는 dp는현재 노드가 루트였을 때의 서브트리 개수를 저장하는 배열입니다.dp[현재노드] = 1이 기본값이며 자식 노드 탐색 후 나온 결과 값을 dp[현재노드]에 더해주는 방식으로 값이 도출됩니다. 이때 재귀함수의 인자로 이전 노드의 인덱스를 가져오는 이유는무방향이기 때문에 무한루프가 도는 것을 방지하기 위한일종의 방문처리라고 생각하면 쉽습니다. 코드77,672 KB / 620 ms / 1389 Bimport java.io.*;import java.util.*;public class ..
문제https://www.acmicpc.net/problem/2533 풀이주어진 간선을 활용해 그래프를 형성하고 최소 얼리어답터 수를 구하기 위해 dp를 이용하는 문제입니다. 1. 입력 간선을 바탕으로 무방향 그래프를 형성할 때노드별 진입차수를 저장하는 배열을 만들어 놓습니다.이를 이용해서 진입차수가 0인 노드를 루트노드로 지정합니다.(해당 문제에서는 루트노드가 1번이라고 나와있진 않지만, 1번이 루트노드로 두어도 정답이긴합니다만 직접 구해보았습니다.) 2. dp는 2차원 배열로 생성합니다.dp[해당 노드][해당 노드가 얼리라면 1, 아니라면 0] = 총 얼리 수(최소)를 저장합니다. 3. 재귀를 돌면서 dp에 값을 저장해 둡니다.현재노드가 얼리라면 얼리가 1개인 것이고, [현재노드][1] = 1;여기서..
문제https://www.acmicpc.net/problem/3151 풀이오름차순 정렬 후2중 for문으로 두개의 수를 찾아주고나머지 수를 이분탐색으로(upper bound - lower bound) 몇 개인지 찾아주었습니다. 코드import java.io.*;import java.util.*;public class Main { static int N; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; ..
문제https://www.acmicpc.net/problem/3987 풀이시작 지점에서 각 방향(북 동 남 서)에 대한 탐색과'/'와 '\'를 만났을 때 문제의 조건에 맞게 방향이 변경되는 점을 고려해서가장 오래 머물렀을 때의 시간을 구하는 문제입니다. 사이클로 인해 멈추지 않고 연산하는 경우는 N*M*2보다 크거나 같을 경우 탈출하는 조건을 주어 해결해줍니다.이유는 해당 문제는 재방문이 가능하며 얼마나 오래 머물렀는지 시간을 재는 문제이기 때문입니다.또한, 배열 내의 총 칸 수(N*M)만큼 방문하고 범위 밖으로 벗어났을 경우 등의 케이스를 넉넉하게 포함하기 위해 곱하기 2를 해주었습니다.이 값보다 클 경우에는 사이클이 발생한 경우이므로 "Voyager"를 출력합니다. 개선조건에 따른 코드 길이 줄이기'..
문제https://www.acmicpc.net/problem/2151 풀이출발지점부터 이동하면서 거울을 만났을 때 방향을 변환하여 목적지점까지 도달하는 문제입력 받으면서 출발 지점과 목적지점 저장출발지점에서 4방향으로 나누어 출발(이때, 가로위치, 세로위치, 현재방향, 거울사용횟수를 넘겨줌)직진하면서, 거울(!)을 발견했다면 좌측과 우측으로 45도 꺾음목적지에 도달하면, 거울을 사용한 개수 출력 코드import java.io.*;import java.util.*;public class Main { static int N; static char[][] map; static List list; static int[] dr = {-1, 0, 1, 0}; static int[] dc ..
문제https://www.acmicpc.net/problem/17835 풀이면접장을 기준으로 면접자에게 도달하는 방식으로 문제를 해결합니다. 입력 받을 때, a→b라면 b→a로 간선 잇기k를 입력 받으며, dist를 0으로 초기화하고 pq에 추가다익스트라 알고리즘(1번만 수행)이후에 dist가 가장 먼 값과 해당하는 면접자(노드)를 저장 코드import java.io.*;import java.util.*;public class Main { static int N, M, K; static int INF = Integer.MAX_VALUE; static long[] dist, res; static PriorityQueue pq = new PriorityQueue((o1, o2) -> (..
문제https://www.acmicpc.net/problem/18223 풀이민준이가 건우가 있는 위치를 거치고 마산에 도착했을 때의 최단거리가민준 → 마산으로 직행하는 최단거리보다 작거나 같다면 OK그렇지 않다면 X를 표시하는 문제 1~N으로 가는 다익스트라와 1~K, K~N으로 가는 다익스트라를 비교하면 됩니다. 코드import java.io.*;import java.util.*;public class Main { static int N, M, K; static List[] graph; static int[] dist; static class Node{ int node; int dist; public Node(int node, int dist)..
문제https://www.acmicpc.net/problem/2917 풀이나무를 기준으로 bfs를 진행하여 각 칸이 얼마나 떨어져 있는지 다익스트라를 진행합니다. 시작 칸(V)에서 J까지 최단거리로 가기 위해서1. 전역 V배열2. 4방 탐색 bfs를 진행3. 현재 값의 거리가 min 보다 작을 경우 min 갱신4. 현재 값이 목적지(J)라면 최단 거리 이므로 min return 코드import java.io.*;import java.util.*;public class Main { static int R, C; static int[][] dist; static char[][] map; static Queue treeList; static int[] dr = {-1, 0, 1, 0..
