BOJ 2573 빙산
·
알고리즘/BOJ
www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 빙하가 2차원 배열로 주어지는데 빙하 상하좌우에 0이 있다면 빙하가 0 하나당 -1씩 줄어든다. 구현하면서 신경 쓸만한 부분은 날짜가 지남에 따라 빙하가 녹는 것, 빙하로 이루는 땅이 2개 이상인지 확인할 것 2개만 신경써주면 된다. if (!vis[nx][ny] && !ar[nx][ny]) ar[cur.first][cur.second]--; else if (!vis[nx][ny]) { q.push({ n..
BOJ 4485 녹색 옷 입은 애가 젤다지?
·
알고리즘/BOJ
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..
BOJ 1238 파티
·
알고리즘/BOJ
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..
BOJ 9370 미확인 도착지
·
알고리즘/BOJ
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 ..
BOJ 2357 최솟값과 최댓값
·
알고리즘/BOJ
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 ..
BOJ 1261 알고스팟
·
알고리즘/BOJ
www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 다익스트라와 BFS를 활용한 최단거리 찾기 문제였다. 이 문제는 다익스트라를 처음 배우고 풀어보려 했었는데 도저히 어떻게 풀어야 할지 몰라서 포기했는데 다익스트라를 좀 더 이해하고 보니 어떻게 활용해야 풀 수 있을지 알았다. 기존 다익스트라는 일차원 배열을 통해 한 노드에서 다른 모든 노드를 가는 최단거리를 구하지만 이번 문제에선 2차원 배열을 통해 각 배열의 최단거리를 구해준다. 입력은 ..