프로그래밍 공부 노트

https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 각 칸에 상어가 있는지 여부를 입력받으며 각 상어의 좌표를 저장한 뒤, 상어가 없는 칸에 대해 상어와의 거리의 최솟값을 계산해 각 최솟값의 최댓값을 출력한다. #include #define INF 0x3f3f3f3f #define MAX_N 50 struct coord { int _y = 0, _x = 0; }; int abs(int n) { return n < 0 ?..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 집의 각 칸을 저장한 배열 map에 대해, map[i][j]에 파이프가 있다고 하자. 만일 map[i + 1][j]가 빈 칸인 경우 파이프를 세로로 움직일 수 있고, map[i][j + 1]이 빈 칸인 경우 파이프를 가로로 움직일 수 있으며, 위의 두 칸과 map[i + 1][j + 1] 세 칸이 모두 빈 칸인 경우 파이프를 대각선으로 움직일 수 있다. 그러므로 집의 각 ..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net bfs를 이용해 가능한 모든 경우를 탐색할 수도 있고, 그리디 알고리즘을 활용해 B를 A로 만드는 연산의 횟수를 구할 수도 있다. - bfs #include #include #define MAX 1e9 using namespace std; int main() { // step: A에서 B로 가기 위해 필요한 연산의 수 // len: 한 step에서 연산이 가능한 수의 개수 int A, B, step = 0, len = 1; // A에서 B로 가는 과정에 존재할 수 있는 수의 집합 queue q; // 문제의 조건을 입력받..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 각 칸에 도착했을 때 사다리 혹은 뱀에 의해 도달하는 칸을 배열 arrive에 저장한 뒤, 칸 i에서 주사위눈 j가 나온 경우 최종적으로 도착하는 좌표를 v[i][j]에 arrive를 이용해 저장한다. 이후 100번 칸에 도착할 때까지 bfs를 시행하면 주사위를 굴려야 하는 최소 횟수를 얻을 수 있으므로 이를 출력한다. #include #include..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 1×1 크기의 공간을 노드로, 상하좌우로 인접한 칸 사이의 관계를 에지로 보면 이 문제는 상어의 좌표에서 먹을 수 있는 물고기의 좌표까지 bfs를 여러 번 실행하는 문제이다. 이 때 먹을 수 있는 물고기를 발견한 경우, bfs를 종료하지 않고 같은 거리에 있는 모든 좌표를 탐색해야 한다. #include #include #include using namespace std; #define M..

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, ..