알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net https://junseok.tistory.com/268 백준 24444 - 알고리즘 수업 - 너비 우선 탐색 1 (C++) 문제 링크입니다. https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 10..

문제 링크입니다. https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 간단한 BFS 문제였습니다. 일반적인 그래프 문제와 같이 백터를 이용해 양방향 간선을 저장해줍니다. 해당 문제에서는 방문하는 노드는 항상 오름차순이라고 정해졌으니, 백터에 저장된 값들을 전부 정렬해줘야 합니다. 정렬을 해준 뒤, 시작점부터 BFS 탐색을 해주면 됩니다. 이때 방문한 순서를 기억해줘야하니, ..

문제 링크입니다. 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..

문제 링크입니다. https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net BFS와 DP가 섞여있는 문제였습니다. 시작하는 좌표와 방향, 끝나는 좌표와 방향이 주어졌을때, 최소한의 명령을 해야지 도착할 수 있는지 구하는 문제입니다. 문제에서 동서남북의 방향을 정해줬기에 해당하는 값을 사용했습니다. 명령에는 2가지 경우가 있습니다. 1. 1~3의 값으로 이동(로봇의 방향 기준) 2. 오른쪽 or 왼쪽으로 90˚ 이동 예를 들어, 오른쪽으로 180º 이동 후, 3칸 ..

문제 링크입니다. https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS와 Dp를 사용해 풀었습니다. 두개의 C를 연결하는데 필요한 거울의 최소 갯수를 구하는 문제입니다. 먼저 거울을 설치했을 경우 레이저가 거울에 따라서 이동 방향이 달라집니다. 하지만 상하좌우 어느 방향에서 레이저가 들어오더라도 레이저의 방향이 대각선으로 변하는 경우는 없기에 이동 방향은 상하좌우만 신경쓰면 됩니다. 상하좌우만 신경쓰면 거울의 설치 갯수도 구하기 쉽습..

문제 링크입니다. https://www.acmicpc.net/problem/14868 14868번: 문명 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(2 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지 www.acmicpc.net 어려웠던 그래프 문제입니다. 해당 문제는 BFS와 Union-Find를 같이 사용해 푸는 문제입니다. BFS만을 통해 풀 수 있는 문제이긴 하지만 N,K값이 크기에 시간 초과가 생길 확률이 높습니다. 문제를 풀기 위해서는 2가지 함수를 만들어야합니다. 1. 문명을 연결하는 함수 2. 문명을 전파하는 함수 1번인 문명을 연결하는 함수의 경우에는 4방향 탐색..

문제 링크입니다. https://www.acmicpc.net/problem/25208 25208번: 새벽의 탐정 게임 새벽의 탐정 게임은 재미있는 2인용 보드게임이다. 한 명은 탐정, 다른 한 명은 도둑 역할을 맡는다. 게임은 $N$행 $M$열 격자 위에서 진행된다. 격자의 각 칸은 벽이 설치되어 있거나 비어있고, 역 www.acmicpc.net 주사위 굴러가는 방향을 신경써주면 풀 수 있는 문제였습니다. 문제에서 생각해야할 점이 있었습니다. 1. 같은 좌표에 방문하더라도 다른 주사위 방향이라면 다른 방향이다. 2. 주사위가 상하좌우 움직였을 때 어떤 방향으로 움직이는가? 이 두가지를 해결할 수 있으면 풀 수 있는 문제입니다. 먼저 1번을 생각해보겠습니다. 윗면에서 (X, Y)를 방문한 것과 아랫면에서 ..

문제 링크입니다. https://www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net BFS를 사용해 푸는 문제였습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; int N, M; char map[251][251]; int check[251][251]; int dx[4] ..

문제 링크입니다. https://www.acmicpc.net/problem/23085 front_coin) continue; if (check[back_coin - reverse_back + reverse_front] == 0) { check[back_coin - reverse_back + reverse_front] = 1; q.push({ back_coin - reverse_back + reverse_front , x + 1 }); } } } return -1; } void solve() { int back = 0; for (int i = 0; i N ..

문제 링크입니다. https://www.acmicpc.net/problem/10552 10552번: DOM The first line of input contains three integers N, M and P (1 ≤ N, M ≤ 105, 1 ≤ P ≤ M), the number of pensioners, the number of TV channels and the initial channel displayed on TV. Each of the following N lines contains two integers ai and bi (1 www.acmicpc.net 추상적인 그래프 표현이였기에 생각보단 어려웠던 문제입니다. 싫어하는 채널이 틀어져 있을 경우 나이가 가장 어린 사람이 자신이 가장 좋아하..

문제 링크입니다. https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net BFS를 이용해 푸는 문제입니다. 먼저 음식물을 배열에 저장해야합니다. 따라서 (X,Y) 좌표에 0이 아닌 다른 수를 저장해줍니다. MAP을 만들었다면 음식물이 있는 곳부터 BFS를 탐색을 시작해줍니다. 탐색 시작의 조건은 음식물이 있으면서 이전에 방문하지 않았을 경우입니다. 탐색을 시작했다면 4방향 탐색을 통해서 음식물의 크기를 확인합니..

문제 링크입니다. https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net BFS를 이용해 푸는 문제입니다. 1번째 열에서 N번째 열까지 갈 수 있는지를 물어보는 문제입니다. 먼저 1번째 열에서 전기가 통하는 곳을 찾습니다. 전기가 통하는 곳을 찾았다면 해당 부분에서 4방향 탐색을 시작합니다. 4방향 탐색 중에서 N번째 열에 도착했다면? -> 탐색을 종료하고 YES를 출력합니다. 탐색이 끝나고도 N번째 열에 도착하지 ..