mojo's Blog

문제 링크 : 25189번: 시니컬한 개구리 (acmicpc.net) 25189번: 시니컬한 개구리 개구리는 $N \times M$ 격자 모양의 청정한 서식지에 살고 있다. 가장 왼쪽 위 칸의 좌표는 $(1,1)$이고 가장 오른쪽 아래 칸의 좌표는 $(N,M)$이다. 각 격자 칸에는 개구리밥이 있는데, 개구리는 자신이 www.acmicpc.net 2022 서강대학교 청정수컵 Round G번 문제이다. 문제 유형은 전형적인 BFS 로 보이지만, 인풋 사이즈로 인해 난이도가 급상승한 느낌이다. N, M 값의 최대값이 100 이였다면 navie 하게 \(O(N^{3})\) 으로 해결이 가능했을 것이다. 그러나, N, M 값의 최댓값이 1000 이므로 navie 한 접근이 불가능하므로 약간의 생각이 필요했다. ..

문제 링크 : 1939번: 중량제한 (acmicpc.net) 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 문제 N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다. 영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다..

문제 링크 : 2842번: 집배원 한상덕 (acmicpc.net) 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다. 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현..

문제 링크 : 17142번: 연구소 3 (acmicpc.net) 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 문제 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은..

문제 링크 => 2573번: 빙산 (acmicpc.net) 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 무난한 DFS 문제이다. 해당 문제에 대한 접근법은 다음과 같다. ⓞ 시간을 1 증가시킨다. (count++) ① 빙산이 있는 지점(x, y)을 확인..

문제 링크 => 15684번: 사다리 조작 (acmicpc.net) 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 삼성 역량 테스트 문제로 BFS + Backtracking 문제이다. 문제 접근방법은 다음과 같다. 1. 위치 (i, j) 에 대하여 함수 f(i, j) 를 해당 위치에 대한 index값이라 할 때 f(i, j) = (i - 1)*N + j 라고 한다. 이때, (i, j) ~ (i, j+1) 의 길을 이어주는 방법은 path[f(i, j)][f(i, j+1)] = path[f(i, j+1)][f..