겜돌이의 개발일지

문제 백준 4485 녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 처음에 오른쪽, 아래쪽으로만 이동 가능한 줄 알고, 'DP로 쉽게 풀리겠네'라고 잘못 생각했다. 상하좌우 이동이 모두 가능하기 때문에 다익스트라로 해결해야 한다. struct 타입을 새로 정의하고 우선순위 큐에 넣으면 비교가 불가하기 때문에 에러가 발생한다. 오퍼레이터를 정의해줘서, 오름차순으로 PQ에 들어가게 해 주었다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

문제 백준 1504 특정한 최단 경로 C++ 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 다익스트라를 사용합니다. 정점 v1, v2를 지나고 1부터 시작해서 N에서 끝나는 경로는 다음 2가지 중 하나입니다. 1) 1 -> v1 -> v2 -> N 2) 1 -> v2 -> v1 -> N 따라서 다익스트라를 3번 사용하여 각각의 최소거리를 구해주고 1)과 2)중 최솟값이 정답이 됩니다. 1), 2)의 경로로 모두 도달이 불가능 할 때 (INF일 때)는 -1을 ..

문제 백준 1967 트리의 지름 C++ 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 dfs를 사용합니다. 1. 1이 항상 루트 노드이므로, 1에서 가장 먼 노드를 찾습니다. 2. 가장 먼 노드에서 다시 dfs를 실행하여, 다른 가장 먼 노드 까지의 거리를 구합니다. 3. 그 거리가 트리의 지름이 됩니다. 트리의 지름을 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..

문제 백준 2573 빙산 C++ 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 일반적인 bfs 문제입니다. 1. melt() 함수로 주변에 바닷물 만큼 빙산의 크기를 감소시켜줍니다. 2. 빙산이 모두 0이 됐다면 0을 출력해줍니다. 3. 빙산이 있다면 (0이 아닌 숫자가 있다면) bfs를 통해 빙산의 개수를 세어줍니다. 4. 빙산의 개수가 2개 이상이라면, 걸린 시간 t를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..

문제 백준 1261 알고스팟 C++ 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 1. 시작점부터 bfs를 실행하여 목적지까지 도달하는 경로를 찾습니다. 2-1. 목적지에 도달하지 못했다면, 이번 bfs를 실행하는 동안 만난 벽(1)들을 빈 방(0)으로 바꿔줍니다. 2-2. 목적지에 도달했다면, 지금까지 실행했던 bfs 횟수 - 1을 출력합니다. 3. 목적지에 도달할 수 있을 때까지 1 ~ 2 과정을 반복합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

문제 백준 3055 탈출 C++ 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 고슴도치의 위치에서 bfs를 실행합니다. time이 늘어날 때만, 물을 확산해줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 ..

문제 백준 1197 최소 스패닝 트리 C++ 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 크루스칼 알고리즘을 이용합니다. 1. 간선들을 가중치 기준 오름차순으로 정렬합니다. 2. 간선의 시작과 끝이 연결되지 않았다면 (부모가 같지 않다면) 연결하고 가중치를 더해줍니다. 2-1. 시작과 끝이 연결된 경우에는 해당 간선은 연결할 필요가 없으므로 무시합니다. 3. 간선 배열을 모두 확인해 준 뒤 답을 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10..

문제 백준 2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 일반적인 dfs, bfs 문제입니다. 저는 bfs로 풀었습니다. 입력을 받고, 사각형이 있는 위치를 1, 없는 위치를 0으로 초기화해줍니다. bfs를 실행하면서 개수와 영역의 넓이를 구합니다. 영역은 vector에 push 해준 뒤, 오름차순으로 정렬하여 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..