기록방

👉 문제링크🔸 문제 분석 🔸1번 도시부터 다른 도시로 가는 K번째 최단 거리를 구해야 한다.K번째 최단 경로가 없으면 -1 출력한다.🔸 문제 풀이 🔸한 노드부터 다른 노드까지의 최단 거리를 구하므로, 다익스트라 (Dijkstra) 알고리즘을 선택한다.일반적인 다익스트라와 다르게, 거리를 업데이트이트 하지 않고 우선 순위 큐에 다시 넣는다.무한 순환 혹은 너무 많은 원소가 생기지 않도록, K개 까지만 거리를 구한다.🔸 코드 🔸import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWrite..

👉 문제링크 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시 중 M개의 도시를 여행하고자 한다. 경로가 있어서 여행이 가능하면 YES, 불가능하면 NO를 출력한다. 🔸 문제 풀이 🔸 여행 하고자 하는 M개의 도시 간에 경로가 있는지 파악하는 쉬운 방법은 같은 집합에 있는지 확인하는 것이다. 분리 집합(Disjoint Set)으로 N개의 도시들의 집합을 나눈다. 여행 계획상의 도시들이 같은 집합에 있으면 경로가 존재한다는 뜻이다. 분리 집합이 아니라 BFS나 DFS로 Brute F..

👉 문제링크 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 🔸 문제 분석 🔸 NxN 게임판에서 뱀이 이동하는 게임이 몇초간 진행 되는지 반환한다. 게임 판에는 K개의 사과가 있고, 사과를 먹으면 몸 길이가 1 늘어나며 기존의 꼬리 위치가 변경되지 않는다. 몸 혹은 게임판 벽에 부딪히면 게임이 종료된다. 🔸 문제 풀이 🔸 특별한 알고리즘이 없는 시뮬레이션 문제이다. 뱀의 방향 전환 정보와 뱀의 꼬리 좌표를 기억하기 위해 큐 자료구조를 사용한다. 🔸 코드 🔸 import java.io.*; import java.uti..

👉 문제링크 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 🔸 문제 분석 🔸 두 배열 A와 B의 부배열의 합으로 T를 만드는 경우의 수를 출력한다. 🔸 문제 풀이 🔸 부배열을 구하는 방법으로 누적합을 이용한다. 입력 배열의 원소는 최대 1,000이므로, int형으로 2개의 배열을 선언해서 2,000 x 4Byte = 8KB가 쓰인다. 배열 A와 B의 누적합을 만든 뒤, 모든 부배열의 합을 구한다. A의 부배열의 수는 A의 원소 ..

👉 문제링크 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 🔸 문제 분석 🔸 n개의 점들 사이에 m개의 선분을 그을 때, 사이클이 생기는 시점을 확인한다. 사이클이 처음 생긴 순서를 출력한다. 사이클이 생기지 않으면 0을 출력한다. 🔸 문제 풀이 🔸 분리 집합(Disjoint Set)을 이용해 사이클이 생기는 시점을 파악한다. 🔸 코드 🔸 import java.io.*; import java.util.StringTokenizer; public class Main { private static int[] ..