https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이 모든 정점에 대해 모든정점까지의 최단거리를 구해야 하기 때문에 그래프 최단거리 알고리즘을 사용했다. 1

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이 한 정점에서 다른 정점으로 최단경로로 이동할 때 가장 먼저 거쳐야 하는 정점을 구해야 하기 때문에 그래프 최단거리 알고리즘(다익스트라)을 응용하여 풀었다. 다익스트라 알고리즘을 진행할 때, 각 엣지에 먼저 거치는 정점도 저장하기 위해 Edge 클래스에 int형 멤버변수 startV를 추가했고, 이후 PQ에 엣지를 추가할 때 이전 엣지의 startV를 세팅하여 저장하는 로직을 추가하였다. static ..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 BFS를 사용해서 출발지부터 목적지까지의 최단거리를 구하면 된다. 최단거리를 총 2번 구하는데, 검을 얻지 않는 상태와 검을 얻은 상태의 최단거리를 구하여 비교한다. 둘 중 더 작은 최단거리가 T보다 작거나 같다면 그 값을 출력하고, 그렇지 않다면 Fail을 출력한다. int bfs(int startR, int startC, int destR, int destC): (star..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 BFS를 응용하여, 첫째 줄의 숫자를 고르면 그 숫자에 둘째 줄에 있는 숫자를 큐에 집어넣는 과정을 반복해서 최종적으로 각 숫자들이 2번씩 포함되는지를 체크하였다. 한 사이클을 찾아내면, 첫째 줄과 둘째 줄이 같은 숫자들을 추가하여 크기를 구하여 최대 크기의 사이클을 계속해서 업데이트하는 로직을 생각했다. 하지만 사이클이 여러 개 있을 수 있고, 각 숫자는 오직 1개 이하의 사이..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 기본적인 그래프 최단거리 문제다. 그래프 최단거리 알고리즘으로는 다익스트라, 벨만포드, 플로이드-와샬이 있다. 1

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이 먼저 배열 값을 입력받을 때 치즈의 개수를 카운트해서 cheese에 저장한다. 그 다음 while문을 사용하여 cheese가 0이 될 때까지 BFS를 수행한다. BFS는 배열의 처음 위치를 시작점으로 삼는다. 0인 경우에는 위치를 큐에 넣어 탐색을 계속하도록 하고, 1인 경우에는 해당 칸 값을 0으로 변경하고 cheese--를 한다. 코드 import java.io.*; import java.util..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 N*N 크기의 배열을 탐색하여 국경선이 열려 연결되는 국가를 찾아내고, 그 국가의 인구 수를 변경해야 한다. 먼저 2중 for문으로 N*N 크기의 배열을 탐색하고, 각 위치마다 BFS를 통해 연결되는 위치들을 찾아내서 인구 수의 총합을 찾아내고 변경해야 한다. main() 함수의 로직 1. N, L, R을 입력받고 N*N 크기의 배열을 할당하고 값을 입력받는다. 2. while..

https://www.acmicpc.net/problem/1325 A 방향으로 연결되는 간선을 추가해야 한다. 코드 (시간초과) import java.io.*; import java.util.*; public class Main { static ArrayList answer = new ArrayList(); static ArrayList graph = new ArrayList(); static int max = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new Stri..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 트리라고 해서 트리 구조를 만들어야 하나? 라고 생각할 수도 있는데, 그래프를 그려서 해결할 수 있다. 인접 리스트로 그래프의 정보를 저장하고, 루트 노드에서부터 DFS또는 BFS로 탐색을 시작하여 아직 방문하지 않은 노드를 찾을 때마다 부모 노드 저장 배열(parent)에 부모 노드 번호를 저장하면 된다. 코드 import java.io.*; import java.util.*; public class Main { static int[] parent; //부모 노드 저장 배열 public static void main(S..

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 1 - 크루스칼(Union & Find 활용) 최소 스패닝 트리를 구하는 알고리즘은 두 가지가 있다. 1. 크루스칼 (Union & Find 활용) 2. 프림 (PriorityQueue 활용) 크루스칼 알고리즘의 매커니즘 -> 크루스칼 알고리즘은 기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다. 주어진 그래프의 모든 간선에 대해서, 간선의 연결비용을 낮은 순으로 오름 차순 정렬한다. 정렬된 간선 순서대로..

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 사용하여 시작 위치에서 도착 위치까지 가는 최소 시간을 구한다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Str..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 최단 경로를 구하는 문제지만, 특정 정점을 지나는 최단 경로의 길이를 구해야 한다. 1번 정점 -> N번 정점의 최단 경로를 구해야 하는데, 두 정점 v1, v2를 거치는 최단 경로를 구해야 한다. 즉 위 조건을 만족하는 1번 정점 -> N번 정점의 최단 경로는 두가지가 있다. 1. 1 -> v1 -> v2 -> N 2. 1 -> v2 -> v1 -> N 그렇다면 각 정점부터 정점까지의 최단 경로를 구해서, 모든..