문제 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 방법 예전에 유명했던 테트리스 비슷한 게임인 뿌요뿌요 관련된 문제이다. 뿌요뿌요는 같은 색깔이 4개 이상 연결되어 있으면 터지며, 터진 후에 위에 있던 뿌요들이 아래로 내려오면서 연결되면 또 터진다. 이를 연쇄라고 한다. 필드의 정보가 주어졌을때 연쇄가 얼마나 일어나는지 계산하는 문제이다. 4개 이상 연결되어 있는 뿌요를 찾는다. 터뜨린다. (빈 칸으로 만든다)..
그래프 탐색
문제 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로..
