알고리즘

www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net BFS + 다익스트라 조합으로 풀면 된다. 기존 다익스트라는 1차원 배열에서 각 정점의 최단거리를 구했지만 이 문제에서는 2차원 배열로 선언해서 각 구간에 가기 위해서 우선순위 큐를 사용해서 최단거리로 갱신하며 이동한다. #include #include #include using namespace std; const int inf = 1e9; int ar[126][126], n; bool vi..

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 응용문제로, 단방향 그래프의 방향을 바꿔서 다익스트라를 돌리면 모든 정점에서 한 정점으로 가는 거리를 구할 수 있다. 따라서 파티장 x가 주어지면 a에서 b로 가는 그래프 외에 b에서 a로 가는 그래프도 입력을 받아주고 각각에 대해서 다익스트라를 사용한 뒤에 두 배열의 합 중에서 가장 큰 값이 정답이 된다. #include #include #include using na..

www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다. 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h) 그다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ..

www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 세그먼트 트리를 활용한 대표 문제 중 하나다. 처음에는 각 쿼리를 최소 트리, 최대 트리로 해줄까 하다가 pair로 한 번에 받아줬다. #include #include #include using namespace std; const int INF = 1e9 + 1; vector ar; vector tree; int n, m, a, b; pair init(int s, int ..

www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 다익스트라와 BFS를 활용한 최단거리 찾기 문제였다. 이 문제는 다익스트라를 처음 배우고 풀어보려 했었는데 도저히 어떻게 풀어야 할지 몰라서 포기했는데 다익스트라를 좀 더 이해하고 보니 어떻게 활용해야 풀 수 있을지 알았다. 기존 다익스트라는 일차원 배열을 통해 한 노드에서 다른 모든 노드를 가는 최단거리를 구하지만 이번 문제에선 2차원 배열을 통해 각 배열의 최단거리를 구해준다. 입력은 ..

www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 시뮬레이션 문제는 왜 이렇게 말을 복잡하게 하는 걸까.. 이번 문제도 이해는 어렵고 구현은 더 어려웠다. 결국 다른 풀이를 참고해서 풀었다. 구현 문제는 풀고 보면 참 쉬운 것 같다.. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에..