프로그래밍 공부 노트

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 연구소의 빈 칸과 벽, 바이러스가 있는 칸을 노드로, 상하좌우로 인접한 노드 사이의 관계를 에지로 보면 이 문제는 그래프 탐색 문제로 볼 수 있다. 이 때 벽을 세 칸 세워야 하므로 브루트포스를 이용해 각 빈 칸에 벽을 세 개 세운 뒤 그래프 탐색을 실행해야 한다. #include #include using namespace std; typedef pair coord; #define MAX_N 8 #defin..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 각 점을 노드로, 수빈이 1초만에 이동 가능한 좌표 간의 관계를 에지로 보면 이 문제는 BFS 문제임을 알 수 있다. 단, 순간이동을 하는 경우 시간 소모가 없으므로 어느 노드를 방문할 때 반드시 해당 노드에서 순간 이동으로 도착할 수 있는 노드를 전부 탐색하여야 한다. #include #include using namespace std; #define MAX_N..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 보드를 기울여 구슬을 움직이는 기능을 구현한 뒤, 보드를 10번 움직여 빨간 구슬만 구멍에 넣을 수 있다면 보드를 기울이는 최소 횟수를, 그렇지 않다면 -1을 출력한다. #include typedef unsigned int ui; #define MAX_N 10 #define MAX_TILT 10 #define INF 0xffffffff class ..

https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 보드를 기울여 구슬을 움직이는 기능을 구현한 뒤, 보드를 10번 움직여 빨간 구슬만 구멍에 넣을 수 있는지 여부를 반환한다. #include #define MAX_N 10 #define MAX_TILT 10 int N, M, add[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int min(int a, int b) {..

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 2부터 차례로 1로 만드는 연산 횟수의 최솟값을 구한 뒤, N의 연산 횟수의 최솟값을 출력하고, N을 세 연산의 결과 X 중 결과 연산 횟수의 최솟값이 가장 작은 X로 바꿔가며 출력한다. #include #define MAX 1000000 #define INF 0x3f3f3f3f char min(char a, char b) { return a < b ? a : b; } int main() { // step[X]: X를 1로 만들기 위한 연산 횟수의 최솟값 char step[MAX + 1] = { 0, ..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 각 점을 노드로, 수빈이 1초만에 이동 가능한 좌표 간의 관계를 에지로 보면 이 문제는 BFS 문제임을 알 수 있다. 단, 이전에 방문한 적이 있는 노드라 하더라도 같은 시간에 방문한 노드라면 경우의 수 계산을 위해 다시 한 번 방문해야 한다. #include #include using namespace std; #define MAX_N 100000 int m..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 각 도시를 노드로, 버스를 방향이 있는 에지로 보면 시작점에서 도착점까지 최소 비용과 경로를 묻는 문제이므로 다익스트라를 이용해 풀 수 있다. #include #include #include using namespace std; #define INF 0x3f3f3f3f #define MAX_N 1000 #define _cost first #define _node s..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리를 입력받은 뒤 bfs를 이용해 트리를 탐색하며 각 노드의 부모 노드를 저장한 뒤 각 노드의 부모를 출력한다. #include #include using namespace std; #define MAX_N 100000 int main() { // 입출력 속도 향상 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // N: 노드의 개수, a, b: 각 에지를 이루는 두 노드, parent[i]: 노드..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 입력으로 주어진 그래프의 개수를 세는 문제이므로, 그래프를 그대로 저장한 뒤 그래프를 탐색해 그래프의 개수를 출력하거나, 그래프에 크루스칼 기법을 적용한 뒤 만들어진 트리의 루트 노드의 개수를 출력하면 된다. - 그래프 탐색 #include using namespace std; #define MAX_N 1000 // graph[i][j..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 모든 노드에서 모든 노드로의 경로를 묻는 문제이므로 플로이드-워셜 알고리즘을 사용한다. #include using namespace std; #define MAX_N 100 #define INF 0x3f3f3f3f // a를 a와 b 중 더 작은 값으로 설정 void set_min(int &a, int b) { a = a < b ? a : b; } int main() { // 입출력 속도 향상 i..