목록알고리즘/백준 (65)
개발자 김수진
[문제] 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..
[문제] www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net [풀이] 길이가 N인 수열이 주어지고 수열의 합의 최댓값을 구하는 문제. 숫자끼리 서로 묶어서 곱하여 더할 수 있다. 단 모든 수는 한번만 묶거나, 묶지 않아야한다. 큰 수 끼리 곱할수록 값이 더 커지므로 처음에는 vector만 사용해서 풀었다. 음수, 양수를 따로 벡터에 저장한 뒤 정렬하여 풀었는데 틀렸습니다가 나오길래 priority_queue를 사용해서 풀었다. priority_queue는 기본..
[문제] www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net [풀이] 모눈종이 위에 치즈가 존재하고 , 치즈가 공기와 접촉하는 변이 2개 이상일 경우 한시간 뒤에 녹게된다. (치즈 내부에 있는 치즈 공간은 공기와 접촉하지 않는 것으로 가정한다. ) 이 때 치즈가 모두 녹는데 걸리는 시간을 구하는 문제이다. BFS를 사용해 외부 공간을 queue에 저장하였다. queue에서 하나씩 pop 할 때마다 해당 좌표의 상하좌우 중에서 치즈가 존재하는지 확인한다...