알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 생각이 필요한 다익스트라 문제였습니다. 목적지 후보지와 출발점, 듀오가 이동한 정점 2개가 주어졌을 때, 어떤 후보지에 향하고 있었는지를 구하는 문제입니다. 이 문제를 풀기 위해서는 S-G or G-S 간선을 이동했는지를 구하는 것이 핵심입니다. 출발점에서 목적지 후보지까지 각각 이동한 간선들을 모두 저장하는 것도 방법이지만, S, G정점 활용해 최소 비용을 비교하는 것이 ..

문제 링크입니다. https://www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net BFS로 풀 수 있는 문제입니다. 1~N번 사람과 연결된 사람들이 주어지고, 루머를 퍼트립니다. 이때 X번 사람이 몇분만에 루머를 믿는지를 구하는 문제입니다. X번 사람이 루머를 믿는 조건은 자신과 연결된 사람 중, 과반수 이상이 믿으면 X번 사람도 믿게 됩니다. 그렇다면 배열 하나를 만들어, X번을 탐색하려고 할 때마다 해당 배열의 값을 ..

문제 링크입니다. https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 다익스트라를 사용해서 푸는 문제였습니다. 1번 점부터 시작해, 2~N번 점까지 각각 최소비용으로 선을 연결시키는 문제입니다. 최소 비용으로 연결했을 때, 복구한 선의 갯수와, 복구된 선을 구해야합니다. 문제에서 선을 복구하는 조건이 있습니다. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 ..

문제 링크입니다. https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net Dp와 다익스트라 알고리즘을 합펴서 푸는 문제였습니다. 이동 비용이 M이하이면서, 최소시간을 구하는 문제입니다. 1에서 N까지 이동할 때, 최소 거리를 구하는 방법은 간단합니다. 하지만, N까지 이동할 수 있는 비용은 다를 수 있습니다. 따라서 2차원 배열을 이동해, X번 노드를 Y비용에 도착했을 경우로 만들어줘야 합니다. 저는 Distanc..

문제 링크입니다. https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 탐색 횟수가 많은 다익스트라 문제였습니다. 시작점에서 마지막점까지 갈 수 있는지를 확인하는 문제였습니다. X번 정점을 갈 수 있는지 여부를 확인한 뒤, 이에 따라 최소 거리를 구해야합니다. N M; for(int i = 1; i > View[i]; } View[N] = 0; for(int i = 1; i > x >> y >> cost; if(View[x..

문제 링크입니다. https://www.acmicpc.net/problem/16509 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 www.acmicpc.net 특이한 8방향 그래프 이동을 통해 원하는 목적지에 도달할 수 있는지를 구하는 문제입니다. 상이 왕을 잡을 수 있는 횟수가 얼마인지를 구하는 문제입니다. 상이 이동할 수 있는 8방향을 통해 계속 이동하면서 왕이 있는 곳까지 움직이면 되는 문제입니다. 주의할 점은 상이 이동하는 길에 다른 말이 있을 경우 해당 방향으로 움직일 수 없다는 것입니다. 해당 조건만 주의하면 쉽게 풀 수 있는 문제입..

문제 링크입니다. https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net BFS의 순서를 확인할 수 있는지를 물어보는 문제였습니다. 1번부터 BFS 탐색을 시작했을 때, 주어진 순서가 올바른 BFS 방문 순서인지를 확인하는 문제입니다. 부모가 같은 노드가 다수일 경우, 방문 순서가 여러개가 나올 수 있습니다. 문제 예시에서는 (1, 2, 3, 4) or (1, 3, 2, 4)가 나올 수 있습니다. 여러개가 나올 수 있는 방문 순서 중 하나가 입력에 주어졌는지를 찾아야합니다. 나올 수 있는 모든 경우를 확인하는 방법보다는 문제에서 나온 경우만을 맞는지 확인하는 것이 효..

문제 링크입니다. https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net BFS와 구현, 브루트포스가 합쳐진 문제였습니다. 문제 자체는 간단하지만 구현 능력이 있어야했던 문제입니다. 5개 층의 Map이 주어지고, 이를 통해 미로를 구성한 뒤 탈출할 수 있는지를 확인하는 문제입니다. 이 문제를 풀기 위해서 구현해야할 것이 있습니다. 1. 5개 층을 선택하기 2. 층을 반시계 혹은 시계 방향으로 돌리기 3. 구성된 미로를 탐색하기 먼..

문제 링크입니다. https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 이전과 이후를 비교하는 문제였습니다. 백신을 맞기 전과 후의 MAP을 주고 백신을 맞은 확률이 있는지를 알아보는 문제였습니다. 백신을 한번만 맞을 수 있다는 것이 중요했습니다. 이전과 이후의 MAP을 비교해서 다른 곳이 하나 있다면 해당 점에서 4방향 탐색을 시작합니다. 탐색을 완료한 뒤에 두개의 MAP을 비교해서 다른 경우 NO, 같은..

문제 링크입니다. https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 4방향 탐색으로 친구를 찾아주는 문제였습니다. 'I'에서 시작해서 4방향 탐색으로 'P'를 찾는 문제였습니다. 'X'를 제외한 모든 곳을 탐색할 수 있음으로 이를 유의하여 문제를 풀면 됩니다. 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #i..

문제 링크입니다. https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 간단한 4방향 그래프 탐색 문제입니다. map이 주어졌을 때, 양 무리가 얼마나 있는지 구하는 문제입니다. 양이 있는 곳을 찾은 뒤, 해당 좌표에서 4방향 탐색을 이어가서 얼마나 양이 이어져 있는지 확인합니다. 탐색이 있을 때마다 양 무리를 하나씩 증가시켜주면 됩니다. 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS ..

문제 링크입니다. https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 브루트포스와 BFS가 합쳐진 문제였습니다. map이 주어졌을때, 상어와 가장 멀리 떨어진 위치를 찾는 곳입니다. 주어질 수 있는 map의 크기가 크지 않기 때문에 모든 곳에서 상어와 떨어진 거리를 확인해보면 되는 문제입니다. for문을 통해, map의 값이 0인 모든 곳에서 8방향 탐색을 시작해 1과 만나면 바로 탈출해주면 됩니다. 이때의 이동거리를 ..