개발자 김수진

[문제] 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 할 때마다 해당 좌표의 상하좌우 중에서 치즈가 존재하는지 확인한다...

[문제] www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net [풀이] S층에서 G층으로 가기 위해 눌러야 하는 버튼 수의 최솟값을 구하는 문제이다. BFS를 사용해 풀 수 있었다. visited 배열을 사용해 이미 방문한 층이라면 넘어가고 처음 방문한 층이라면 이전 층의 버튼 수 +1 을 저장한다. 이렇게 while문을 진행하다가 G 층을 만나면 버튼 수를 출력하고 BFS 함수를 return 한다. queue가 empty가 되어 while문이 끝나는 경우 엘레베이터로 이동할..

[문제] www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net [풀이] 상하좌우 중에서 같은 색깔의 뿌요가 4개 이상 존재한다면 뿌요는 터지게 된다. 뿌요들이 터지고 나서 위에 다른 뿌요들이 있다면 중력의 영향을 받아 차례대로 아래로 떨어지게 된다. 먼저 BFS 함수에서 상하좌우에 같은 색깔의 뿌요가 존재하는지 확인한다. 존재한다면 vector에 push 하여서 queue가 empty가 될 때까지 진행한다. while문을 빠져나와서 벡터의 사이즈가 4보다 크거나 같다면 뿌요가 터질 수 있는 조건을 성립하므로 뿌요가 존재하는 위치의 값을 0으로 upd..