문제 https://www.acmicpc.net/problem/25195 25195번: Yes or yes 첫째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($1 \leq N, M \leq 100\,000$) 이후 $M$줄에 걸쳐서 간선의 정보를 나타내는 두 정수 $u$, $v$ 가 주어진다. 이는 정점 $u$ 에서 정점 $v$ 로 가는 www.acmicpc.net 풀이 BFS, DFS 문제입니다. 문제의 포인트는 팬클럽 곰곰이를 거치지 않고 더 이상 이동할 수 없는 간선까지 도달할 수 있는가? 입니다. 우선 팬클럽 곰곰이의 정점을 boolean[] gomgom 배열에 저장해두었습니다. 그리고 BFS 탐색시에 gomgom 배열을 체크합니다. 만약 현재의 정점이 gomgom[] 배열의 t..
Java
문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 BFS 문제입니다. 구역의 개수가 2이상이거나, 얼음이 존재하지 않을 때까지 반복문을 통해 얼음을 녹여야 합니다. addIce() meltIce() checkBlock() 의 세 가지 메서드 순서로 분리해서 문제를 해결했습니다. addIce()는 map[][] 배열의 얼음을 queue 자료 구조에 집어 넣는 메서드입니다. 그리고 동시에 다음 연도에 얼마나 줄어들지를 카운트해서 de..
문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 백준 11053. 가장 긴 증가하는 부분 수열의 문제와 매우 유사한 DP 문제입니다. 더보기 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = ..
문제 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 풀이 정수의 성질을 이용한 문제입니다. 30의 배수인지 체크하기 위해 두 가지 조건을 만족해야합니다. 입력 값에 0이 있는지 30의 배수는 0을 반드시 포함합니다. 입력받은 수에 0이 없다면 -1을 출력합니다. 각 자리 수의 합이 3의 배수인지 3의 배수는 각 자리 수를 더했을 때, 그 총합도 3의 배수인 성질이 있습니다. 그리고 주의해야할 점이 하나있는데 N은 최대 10의 5승의 숫자로 구성..
문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 하나의 지도 배열에 BFS가 두 번 쓰이는 문제입니다. 전형적인 BFS 문제에 물이 퍼지는 것을 고려해야하는 문제입니다. 특정 좌표에 몇 초 후에 물이 도달하는 지는 BFS를 통해 미리 구할 수 있습니다. time[][] 이라는 배열을 선언하여, 물이 미래에 도착할 시간을 저장하고, 고슴도치의 시간(depth)와 물이 도착하는 시간(time[][])을 비교해 문제를 해결했습니다. 소스코드 impor..
문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 소스코드 import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; public class Main { static int N,M,X; static int INF = Integer.MAX_VALUE; static int[] ..
