문제 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net 문제 풀이 빙산의 높이가 주어질 때, 1년이 지날 때마다 바다에 인접한 수만큼 빙산이 녹아서 없어진다. 이때 빙산의 영역이 2개 이상이 되는 최소의 시간(년)을 찾는 문제이다. 문제를 풀기 위해서는 BFS를 통해 영역을 탐색함과 동시에, 각 빙하가 바다와 인접하고 있는 수를 카운트하여 해결할 수 있다. BFS를 통해, 빙하인 부분부터 탐색을 시작한다. 빙하 주위가 바다라면, 딕셔너리를 통해 해당 지점을 카운트한다. BFS 탐색 후에, 탐색 가능한 ..
문제 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치�� www.acmicpc.net 문제 풀이 NxN에 시험관에 바이러스들이 있을 때, 바이러스의 종류는 1부터 K까지 존재한다. 이때, 1번 바이러스부터 우선적으로 전염될 때, S초에 X, Y에 전염된 바이러스의 종류를 출력하는 문제이다. 초기에 전염되지 않은 곳은 0, 바이러스가 있는 곳은 1 ~ K 사이의 수로 표시된다. BFS를 통해 탐색하여 문제를 풀 수 있다. 최초에 주어진 시험관에서 바이러스의 종류를 찾고, 좌표를 기록한다. 1번 바이러스 부터 전..
문제 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경�� www.acmicpc.net 문제 풀이 블루레이에 N개의 레슨이 들어가는데, 블루레이를 녹화할 때는 레슨의 순서가 바뀌면 안 되고 M개의 블루레이에 플레이 타임이 모두 같도록 해서 만들어야 한다. 이때 가능한 블루레이의 크기 중 최소를 출력하는 문제이다. 이 문제는 전형적인 이분 탐색 문제이다. start, end를 `max(lesson)`, `sum(lesson)`로 설정한다. 하나의 레슨을 담고자 한다면 최소 lesson에서 가장 큰 값은 되어야 한다. 하나의 블루레이에 모든 레슨을 ..
문제 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 풀이 문제에 F, S, G, U, D `(건물의 높이, 시작층, 가고자 하는 층, 한 번에 올라가는 층, 한 번에 내려가는 층)`가 주어진다. 시작 층에서 엘리베이터를 이용해 가고자 하는 층에 도달하는 최소 경우를 반환하는 문제이다. 만약 도달할 수 없다면 계단을 이용하라는 메시지를 출력한다. BFS를 통해 시작층 부터 올라가는 경우, 내려가는 경우를 탐색한다. 올라가는 경우 F보다 작거나 같아야 하며, 내려가는 경우는 0 보다 커야 한다. 재방문을 막기 위해 현..
