Algorithm/Simulation

[백준 16234번] 인구 이동 (C/C++)

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 인구 이동 문제는 BFS를 이용하여 해결했습니다. 각 좌표를 시작점으로 BFS를 수행하여, 인구 차이가 L명 이상, R명 이하인 연합을 찾고, 각 연합에 대해 인구 이동을 시킨 뒤, 다시 BFS를 수행합니다. BFS를 수행하고 나서 더이상 연합이 존재하지 않는다면, 종료하면 됩니다. 전체 코드는 아래와 같습니다. #include using namespace std; #define x..

[백준 17281번] ⚾ (C/C++)

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 야구 게임 문제는 큐와 백트래킹을 이용하여 문제를 풀 수 있습니다. 백트래킹을 이용하여 타순의 모든 경우의 수를 구하고, 각 타순에 대한 게임 결과를 계산하면 됩니다. 알고리즘의 기본 틀은 아래와 같습니다. 타순의 각 경우의 수에 대해 게임을 진행한다. (단, 1번 타자를 제외한 permutation을 구한다.) 타순의 4번 타자에 1번 선수를 넣는다. 게임을 시작한다. 3-1) 이닝을 시작한다. (단..

[백준 5373번] 큐빙 (C/C++)

https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 큐빙 문제는 큐를 이용하여 해결하였습니다. 큐브를 돌릴 수 있는 부분을 모두 큐로 만든 뒤, 큐브를 돌릴 때마다 해당 큐를 돌려주고, 돌아가는 면을 rotate 해주면 됩니다. 아래 그림은 큐브의 전개도와 각 큐를 도식화한 이미지입니다. 1은 아랫 면, 2는 뒷 면, 3은 왼쪽 면, 4는 앞 면, 5는 오른쪽 면, 6은 윗 면입니다. ⚠️ 단, 각각의 큐가 서로 공유하는 면이 존재하기 때문에 큐를 ..

[백준 15685번] 드래곤 커브 (C/C++)

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 드래곤 커브의 n번째 세대는 n-1번째 세대를 시계 방향으로 90도 회전시킨 다음, 드래곤 커브의 끝 점에 붙여준 것이기 때문에 n - 1 세대의 방향 정보가 담겨있습니다. 다만, 90도 회전시켜 붙여주기 때문에 n번째 세대의 새로 추가된 선분의 방향은 이전 세대 방향의 순서를 역순으로 한 후, (이전 세대의 각 방향 + 1) % 4 해주면 됩니다. 예를 들어 2세대의 ..

[백준 15684번] 사다리 조작 (C/C++)

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 사다리 조작 문제는 백트래킹을 이용하여 가로선을 선택하는 모든 경우의 수(Combination)에 대해 사다리 타기를 수행하면 문제를 해결할 수 있습니다. 전체 코드는 아래와 같습니다. #include using namespace std; #define b first #define a second int board[30][10]; // board[b-1][a-1]은 b번과 b+1번을 연결하는 a..

[백준 14890번] 경사로 (C/C++)

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 경사로 문제의 전체 틀은 아래와 같습니다. 각 행과 열의 각 좌표를 한 칸씩 진행하면서 확인한다. 다음 칸이 현재 칸 보다 높으면, 이전 ~ 현재 칸에서 경사로가 설치되지 않았으면서, 현재 칸과 높이가 같은 연속된 칸의 개수를 계산한다. 칸의 개수가 l보다 크면 한 칸 이동한다. 크지 않으면 지나갈 수 없다. 다음 칸이 현재 칸 보다 낮으면, 다음 칸 ~ 마지막 칸 에서 경사로가 설치되지 않았으면서, 다음 칸과 높이가 ..

[백준 14502번] 연구소 (C/C++)

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 연구소 문제는 (빈칸의 개수) C 3개의 경우의 수를 구하고, 각각의 경우의 수에 대해 BFS를 수행하면 해결할 수 있습니다. 아래는 전체 코드입니다. #include using namespace std; #define x first #define y second int n, m, ans = INT_MIN; int board[8][8]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {..

[백준 13460번] 구슬 탈출 2 (C/C++)

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 구슬 탈출은 네 가지 동작을 최대 10번 수행하는 모든 경우의 수를 실행해보면 됩니다. HTML 삽입 미리보기할 수 없는 소스 예를 들어, {위, 아래, 오른쪽, 왼쪽, 왼쪽, 왼쪽, 왼쪽, 왼쪽, 왼쪽, 왼쪽}, {위, 아래, 오른쪽, 왼쪽, 왼쪽, 왼쪽, 왼쪽, 왼쪽, 왼쪽, 왼쪽} 두 가지 경우의 수가 있을 때, 각각의 경우의 수에 대해 독립..