목록알고리즘 (89)
개발자 김수진
[문제] www.acmicpc.net/problem/2931 2931번: 가스관 러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다. www.acmicpc.net [풀이] 맞아서 기분이 좋긴 하지만 뭔가 찝찝하다. 3 5 . . . . . . M . Z . . . . . . 위와 같은 예제는 답이 제대로 나오지 않는다. 시작점을 기준으로 DFS 함수를 통해 한칸씩 나아가도록 하였다. 이 때 현재 위치의 값이 '.' 이라면 solve 함수에서 해당 위치에 들어갈 값을 찾도록 하였다. [코드] 시간 : 0ms #include #define MAX 26 using namespace ..
[문제] www.acmicpc.net/problem/1756 1756번: 피자 굽기 월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 www.acmicpc.net [풀이] 오븐의 지름, 피자 반죽의 지름이 주어지고 마지막 피자 반죽의 위치를 출력하면 된다. 처음에는 완전 탐색으로 풀까 생각했는데 N,D의 최댓 값이 300,00이라서 시간초과가 나오게 된다. 따라서 dp 방법을 사용해 구현했다. depth 라는 배열에 해당 깊이에 구워질 수 있는 피자 지름의 최댓값을 저장했다. 문제 예제로 보면 7 3 5 6 4 3 6 2 3 3 2 5 depth 배열의 값은 5 5 4 ..
[문제] www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [풀이] 수빈이의 위치 N, 동생의 위치 K가 입력으로 주어지고 수빈이가 동생을 찾는 최단경로를 구하는 문제. 이 때, 수빈이는 현재 위치 X 에서 X-1,X+1,2*X로만 움직일 수 있다. 최단경로를 찾아야 하므로 BFS를 사용했다. 현재 위치 X에서 X-1,X+1,2*X로 움직이도록 하였고 visited 배열을 사용해 재방문 하지 않도록 했다. 또한 경로도 구해야 ..
[문제] www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net [풀이] 두 보물간의 최단거리를 구하는 문제. 최단거리를 구하는 문제이길래 BFS를 사용해서 풀려고 했다. 하지만 보물의 위치가 어딘지 몰라서 시작점과 도착점을 설정하는 데 있어 어려움을 겪었다. 생각해보니 map의 최대 사이즈는 50*50이라서 모든 육지에 대해서 시작점으로 잡고 최단거리를 구해도 되겠다고 생각을 하였다. 따라서 모든 육지에 대해 출발점으로 잡고 BFS 함수에서 최단거리를 구해 그 중에서..
[문제] www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net [풀이] 매 초마다 불은 상,하,좌,우 방향으로 퍼져 나간다. 이 때 상근이가 탈출하는데 걸리는 시간을 구하는 문제이다. 처음에는 불이 퍼지는 함수랑 상근이가 움직이는 함수를 따로 만들어서 풀었다. DFS를 사용해 상근이가 움직이도록 했는데, DFS로 움직일 때마다 map을 저장하기 위해 배열을 하나 더 지역변수로 선언했다. 하지만 map의 크기가 워낙 커서 계속 오류가 났다. 두번째 방법으로 BFS 함수에서 불이..
[문제] www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net [풀이] 섬을 연결하는 다리를 설치할 수 있는데, 가장 짧은 다리 하나를 설치할 수 있다. 이 때 가장 짧은 다리의 길이를 구하는 문제. 처음에는 섬을 분리하여, 섬의 가장자리에서 다른 섬의 가장자리로의 최단 거리를 구하려고 했다. 생각해보니 가장자리를 따로 구하지 않고 , BFS를 통해 최단 거리를 구하면 하나의 섬의 가장자리에서 다른 섬의 가장자리까지의 거리가 된다. 따라서 DFS 함수에서 각 섬을 구분..
[문제] www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net [풀이] 판다는 대나무를 다 먹어 치우면 상,하,좌,우 중 하나로 이동할 수 있다. 단, 이전에 먹었던 대나무보다 많은 대나무가 존재하는 곳으로만 이동할 수 있다. 판다가 최대한 살 수 있는 일수를 구하면 된다. DP 배열에 해당 위치에서 이동할 수 있는 최대 거리를 저장했다. 따라서 DFS 함수를 통해 미리 DP 배열의 값을 구해놨다면 DP 배열에 저장된 값을 return 하면 된다. 아직 ..
[문제] www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [풀이] 보드의 정보가 입력으로 주어지고 , 10번 이하의 움직임으로 빨간공이 빠져나갈 수 있으면 1을 출력하고 없으면 0을 출력한다. 먼저 입력으로 보드의 크기와 상태를 입력받았다. 장애물인 있는 좌표는 map에 -1을 저장하고, 구멍이 존재하는 좌표는 1을 저장했다. DFS를 사용해서 풀었다. DFS 함수에서 인자 값으로 몇 번 움직였는지를 나타내는 c..