알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14461 14461번: 소가 길을 건너간 이유 730에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다.www.acmicpc.net다차원 배열을 사용하는 다익스트라 문제입니다.소가 길을 건널 때, 주어진 조건에 따라 최소 시간을 구하는 문제입니다. (1, 1) ->(N, N)으로 가면서, 3번째 방문하는 곳은 항상 풀을 먹어야 합니다. 이동할 때마다 이동시간 T가 추가됩니다. 항상 최단 횟수로 갔을 때, 최소 비용이 나온다는 보장을 할 수 없습니다.(위의 예시가 그렇습니다.) 따라서 다익스트라를..

문제 링크입니다. 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/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net 주어진 map에서 흰 돌을 2개 놓을 때, 검은색 돌을 최대한 많이 죽을 수 있는 개수를 구하는 문제입니다. 돌을 놓을 수 있는 곳에 모두 놓아본 뒤, 잡을 수 있는 돌의 개수를 전부 확인해보면 됩니다. 1. 2개의 돌을 차례대로 놓는다. 2. 돌을 놓은 뒤, 검은 색 돌을 몇개를 잡을 수 있는지를 확인해본다. 3. 모든 경우를 확인한 ..

문제 링크입니다. 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/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 플로이드 와샬을 이용해 푸는 문제입니다. 2-친구를 찾는 문제입니다. 2-친구가 되기 위해서는 X와 Y가 서로 친구이거나, X와 Y가 한다리 건너서 이어져 있으면 됩니다. X에 대해 남은 사람들이 몇번을 건너서 친구가 될 수 있는지를 확인하기 위해서 플로이드 와샬 알고리즘을 이용하면 됩니다. 플로이드 와샬 알고리즘을 사용한 후, Distance[i][j]의 값이 2이하라면, 2-친구..

문제 링크입니다. https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 플로이드 와샬 혹은 DFS를 이용해 풀 수 있던 문제입니다. 플로이드 와샬로 푸는 문제였지만, DFS를 이용하면 더 쉽게 풀 수 있었습니다. 1~N번까지 무게의 비교가 주어질 때, X번 물건과 비교할 수 없는 물건이 몇개인지를 구하는 문제였습니다. 그렇다면, 전부 비교할 수 없다면 값은 N-1이 될 것입니다. 여기서, 자신보다 큰 물건과 작은 물건의 갯수..

문제 링크입니다. 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/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/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net DFS를 이용해 푸는 문제입니다. 윗 줄의 숫자를 하나씩 선택할 때마다, 밑에 붙어 있는 숫자도 같이 선택됩니다. 윗 줄의 숫자를 선택해, 밑의 줄의 숫자와 같게 뽑으려고 할 때 몇 개, 어떤 숫자를 뽑아야하는지 구하는 문제입니다. 이 문제를 푸는 핵심은 윗 줄과 아랫 줄의 숫자를 연결해주는 겁니다. 만약 윗 줄이 1, 아랫 줄이 3이라면, connect[1] = 3..