문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 방법 입력이 주어졌을 때 치즈가 몇 시간만에 녹을지 계산하는 문제이다. 치즈는 4변 중에서 적어도 2변 이상이 외부 공기와 닿으면 정확히 1시간만에 녹는다. 치즈로 둘러싸인 내부 공기는 녹는데에 아무런 영향을 미치지 않는다. 그렇다면 내부 공기와 외부 공기를 어떻게 판별할까? 문제에서 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는다고 했으니, 가장자리에서 공기 칸 탐색을 시..
프로그래밍
문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 방법 어느 섬에서 다른 섬에 도달했을 때의 최소 거리를 구해야하는 문제다. N = 100이하이기 때문에 막연하게 생각해봤을 때 O(N^3)이여도 문제가 없을 것 같아 고안해낸 풀이는 다음과 같다. 떨어져 있는 섬끼리 구분하기 위해서, 각 섬에 그래프 탐색을 이용해서 번호를 붙인다. 번호 붙인 섬마다 BFS로 퍼져나가면서 탐색 탐색 중 다른 섬을 만났을 때 거리를 비교해보고 최소일 경우 ans..
문제 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 풀이 방법 2차원 공간을 탐색하면서 문서 몇 개를 훔칠 수 있을까를 계산하는 문제다. 이 문제만의 특이한 점은 다음과 같다. 처음 시작점이 정해져 있지 않고 주어진 2차원 공간 밖 아무데서나 시작할 수 있다. 열쇠를 얻으면 그에 알맞는 문을 열고 지나갈 수 있다. 열쇠는 알파벳 a~z까지 있으므로 총 26개다. 첫 번째는 주어진 2차원 공간 밖의 테두리를 빈 공간으로 만들어준다. 크기를 h+2, w+2로..
문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 방법 벽을 부쉈을 때 이동할 수 있는 칸의 갯수를 구하면 되는 문제다. 단, 모든 벽마다 탐색을 해서 이동할 수 있는 칸 개수를 구하면 시간 초과가 발생한다. 예를 들어 다음과 같은 케이스가 들어온다고 해보자. 예시: 6 6 101010 000000 101010 000000 101010 000000 1에서 탐색을 시작할때마다 모든 0의 개수를 반복적으로 구하기 때문..
