알고리즘 모음(C++)

문제 링크입니다. 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/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/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/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 비트연산자를 이용해 풀 때 다른 방법보다 쉽게 풀 수 있는 문제입니다. 서쪽은 1, 북쪽은 2, 동쪽은 4, 남쪽은 8의 값을 가질 때, 한 칸마다 수가 주어지는데 해당 하는 수를 통해 어디가 벽으로 막혀있는지를 알 수 있습니다. 예를 들어, 11인 경우 남쪽 + 북쪽 + 서쪽이 벽이 막혀있는 것을 구할 수 있습니다. 그렇다면, 벽이 어디있는지를 알아야하니 합의 조합을 통해..

문제 링크입니다. https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 순환되는 그래프를 찾을 수 있는지를 물어보는 문제였습니다. DFS와 BFS를 함께 써야했던 문제입니다. 그래프가 양방향으로 주어집니다. 주어진 그래프는 순환하는 지점이 만들어지는데, 해당 지점에 속하지 않은 정점과 순환하는 곳과의 거리를 구하는 문제입니다. 그렇다면, 2가지를 구해야하는데 1. 순환하는 지점을 구해야한다. 2. 속하지 않는 지점과 순환하..

문제 링크입니다. 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/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net Dp로 풀 수 있지만, BFS로 푸는게 더 간단해 보여 약간의 노다가를 추가한 BFS로 풀었습니다. 3개의 SCV가 각각 9 or 3 or 1의 값이 빼집니다. 따라서 모든 경우를 확인한 뒤, 전부 0이 된 최소 횟수를 출력해주면 됐습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #inclu..

문제 링크입니다. https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 다익스트라를 사용한 문제입니다. 문제를 풀기위해 새로운 접근이 필요했습니다. 상근이가 두 죄수를 탈옥하기 위해 열어야하는 최수 문 갯수를 구하는 문제입니다. 실수할 수 있는 부분이 있어, 많이 틀렸던 문제입니다. 문제에서 문을 열 수 있는 사람은 상근이와 두 죄수입니다. 그렇다면 생각할 수 있는 경우는 3가지입니다. 1. 상근이만 문을 열어 죄수들을 데려갈 경우 2. 죄수1이 죄수2를 데리고..

문제 링크입니다. https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 생각을 해야되는 BFS 문제였습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #define P pair #define PP pair #define F..