목록알고리즘/백준 (65)
개발자 김수진
[문제] 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..
[문제] www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net [풀이] 하반기 어느 기업 코테에서 굉장히 이 문제와 유사한 문제가 나왔었다. 현재 위치를 기준으로 왼쪽과 오른쪽으로 나누고 그 중에서 가장 큰 값을 left, right 변수에 저장한다. left와 right 중에서 작은 값을 고르고 여기서 현재 블록의 높이를 빼주면 해당 블록의 고이는 빗물의 양이 된다. 위와 같은 방식으로 두번째 블록부터 마지막 블록 전까지 반복해주면 된다. [코..
[문제] www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [풀이] DP 배열을 2차원을 선언하여 풀었다. DP[i][j]는 i자리 수에서 마지막 숫자가 J인 경우의 수를 나타낸다. 예를 들어 DP[2][2]는 'X2'인 경우로 12,32가 있으므로 2이다. 따라서 계단 수를 구하는 것이므로 점화식을 아래와 같이 세울 수 있다. DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]; 단 , j가 0이거나 9인 경우 따로 예외처리 해줘야된다. [코드] #include #define MAX 101 #define MOD 1000000000 using namespa..
[문제] www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net [풀이] 고슴도치가 비버의 굴로 이동해야 하는데 물이 있거나 돌이 있는 곳으로는 움직일 수 없다. 물은 매 분마다 인접한 곳으로 퍼진다. 단 , 비버가 존재하는 곳이나 돌이 존재하는 곳으로는 퍼질 수 없다. 이 때 최단 거리를 구하는 문제. 고슴도치의 이동경로를 저장하는 visited 배열과 물, 돌의 정보를 저장하는 map을 선언했다. BFS 함수의 while 문에서 물이 먼저 퍼지고 그 다음에 고슴도치가 움직이..
[문제] www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] 미로의 정보가 입력으로 주어지고 시작점 (1,1)에서 도착점(N,M)까지의 최단거리를 구하는 문제이다. 1은 이동할 수 있는 칸을 의미하고, 0은 이동할 수 없는 칸을 의미한다. BFS를 사용해 풀었다. 다음 위치의 값이 1인 경우에만 좌표를 queue에 저장하였고, 이미 방문했던 곳이라면 queue에 담지 않았다. 실수했던 부분이 BFS는 동시에 움직이므로 최단거리를 구하는 경우 재방문 하지 않아도 된다. [코드] 시간 :..
[문제] www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net [풀이] 1번 컴퓨터가 바이러스에 걸렸고 1번 컴퓨터와 연결된 컴퓨터는 모두 바이러스에 걸리게 된다. 이 때 1번은 제외하고 바이러스에 걸린 컴퓨터의 갯수를 출력하면 된다. 문제는 DFS를 사용해서 풀 수 있었다. map이라는 2차원 배열을 선언하여 연결 정보를 저장했다. 그 다음 DFS를 1번부터 시작하여 start와 연결된 모든 컴퓨터에 대해 DFS 함수를 호출한다. visited를 통해서 이미 방문했는..
[문제] www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net [풀이] NXM으로 표현되는 맵이 문제 입력으로 주어진다. 맵에는 벽이 존재하는데 최대 한번 벽을 부수고 이동할 수 있다. 이 때 시작점에서 (N,M)까지의 최단 거리를 구하면 된다. 최단거리를 구하는 문제라서 BFS를 사용하고 pos 구조체에 crash 변수를 추가하여 이전 경로에서 벽을 부수고 왔는지를 확인했다. 원래 visited 배열은 2차원 배열로 아래와 같이 선언했었..