알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/31849 BFS를 이용한 문제입니다. 편의점의 위치와 자취방의 위치가 주어졌을 때, 편의점과 자취방의 가장 가까운 거리를 구하는 문제입니다. 거리를 구하는 수식 -> 자취방에서 편의점까지의 거리 * 월세 입니다. 문제를 풀기 위해서는 모든 자취방과 편의점 사이의 거리를 구하면 된다라는 생각을 할 수 있습니다.하지만, 방과 편의점의 최대 개수가 5*10^5 이기에 모든 경우를 탐색한다면 시간 초과가 생길 것입니다. 한번 생각을 해보면, 어떤 편의점에서 출발을 하든 어떤 자취방에 먼저 도착하는 곳이 있다면 해당 편의점이 해당 자취방과 가장 가까운 곳이라는 것이 됩니다. 그렇다면, 모든 편의점에서 동시에 출발해서 각각의 자취방까지 도..

문제 링크입니다. https://www.acmicpc.net/problem/2152 2152번: 여행 계획 세우기첫째 줄에 네 정수 N, M, S, T가 주어진다. 다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1 ≤ A, B ≤ N)가 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 항공www.acmicpc.netSCC 알고리즘과 BFS, DP가 사용된 문제입니다.S도시에서 시작해 T도시에 도착할 때, 여행할 수 있는 최대 도시 수를 구하는 문제입니다. 도시는 한번만 방문 가능한 것이 아닌 여러번 방문할수 있습니다.(여러 번 방문했다고 해도 방문한 도시의 수는 1개만 증가합니다.) 만약, ’도시들 중에 순환이 가능한 도시들이 있다면 해당 도시들을 하나의 그룹으..

문제 링크입니다. https://www.acmicpc.net/problem/2151 2151번: 거울 설치첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net다차원 배열을 이용한 BFS로 풀 수 있는 문제였습니다.두 개의 문이 있을 때, 거울을 이용해 한쪽 문에서 다른 문을 볼 수 있도록 할려고 한다면 몇개의 거울을 사용해야되는지 구하는 문제입니다. 먼저 2개의 문의 위치를 저장한 뒤, 한 쪽 거울에서 BFS 탐색을 시작해줍니다. 여기서는 거울의 설치 갯수를 물어보는 문제이니, 배열 하나를 만들어 큰 값을 저장해줍니다. 그러..

문제 링크입니다. https://www.acmicpc.net/problem/13903 13903번: 출근 첫 번째 줄에는 보도블록의 세로, 가로 R, C(1 ≤ R, C ≤ 1,000)크기가 주어진다. 다음 R개의 줄에는 C개의 문자로 이루어진 보도블록의 초기 상태가 주어진다. (가로 블록은 0로 표시되고, 세로 블록 www.acmicpc.net BFS를 이용한 문제입니다. 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #define INF 987654321 #define F first #define S second using namespace std; int R,..

문제 링크입니다. https://www.acmicpc.net/problem/17025 17025번: Icy Perimeter Please output one line containing two space-separated integers, the first being the area of the largest blob, and the second being its perimeter. If multiple blobs are tied for largest area, print the information for whichever of these has the smallest per www.acmicpc.net 영문으로 되어있는 문제이지만 간단했습니다. 문제를 해석해보자면, '#'으로 연결된 가장 큰 그룹을 ..

문제 링크입니다. https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 다른 BFS와 달리 map의 N번째 칸에 도달했을 때, 더 이상 이동못하는 것이 아닌, 1번째 칸으로 이동하게 됩니다. 이를 코드로만 짤 수 있다면 나머지는 다른 BFS문제와 같게 푸시면 됩니다. 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #..

문제 링크입니다. https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 산봉우리의 갯수를 구하는 문제입니다. 여기서 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격좌들의 집합이라고 정의합니다. 산봉우리와 인접한 격좌는 모두 산봉우리의 높이보다 작아야한다고 합니다. 예시를 통해 산봉우리를 확인해본다면 해당 그림과 같이 3개가 됩니다. 따라서, 1이상의 같은 격좌로 이루어져 있으며, 8방향으로 이어지고, 주변보다..

문제 링크입니다. https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 비트마스킹과 BFS를 이용해 풀 수 있는 문제입니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #define P pair #define F first #define S second using namespace std; int N, M; char map[21][21]; int check[..

문제 링크입니다. https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 규칙을 구하는 것이 난이도를 높였던 것 같습니다. ※pow() 함수를 사용하면 시간초과가 됩니다. (1 (1, 4) / (2, 1) -> (1, 3) / (3, 1) -> (1, 2) / (4, 1) -> (1, 1) (1, 2) -> (2, 4) / (2, 2) -> (2, 3) / (3, 2) -> (2, 2) / (4, 2) -> (2, 1) (1, 3)..

문제 링크입니다. https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net BFS를 이용한 구현 문제였습니다. 3개의 좌표를 동시에 옮겨야 했었기에 코드가 복잡해진 것 같습니다. 나무가 3개의 좌표가 연달아서 주어집니다. 그렇다면 움직일 때 3개의 좌표를 같이 움직여서 다른 위치로 갈 수 있는지를 확인해야합니다. 다른 좌표로 이동할 때 고려해야할 점이 2가지 있는데, 1. 이동한 3개의 좌표에 다른 나무가 없어야한다. 2. 이전에..

문제 링크입니다. https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 그래프 탐색을 이용하는 문제입니다. 노드를 하나 지웠을 때, 리프 노드를 구하는 문제입니다. 시작 노드를 찾은 뒤, 시작 노드에서 그래프 탐색을 시작해줍니다. 탐색 노드와 연결된 노드 중, 연결되지 않는 노드로 이동해 다음 노드로 계속 이동해줍니다. 더 이상 이동할 수 없는 노드로 도착하면, 리프 노드 갯수를 1 증가해줍니다. 여기서, 지워진 노드가 연결되어 있어도 이동할 ..

문제 링크입니다. https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net BFS 혹은 DFS를 통해 푸는 문제였습니다. 물통의 물을 옮겨 C물통의 경우를 구하는 문제입니다. 물통을 옮기는 경우를 생각하면 문제 풀기가 쉬워집니다. 1. A에서 B 2. A에서 C 3. B에서 A 4. B에서 C 5. C에서 A 6. C에서 B 이렇게 6가지입니다. 하지만 경우마다 2가지로 나눠서 생각해야합니다. 1. X물통을 Y에 옮겨도 Y물통이 전부..