문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 구현, 시뮬레이션, 너비 우선 탐색 각 칸에 대해서 연합을 이룰 수 있는지 확인하기 위해, 각 칸의 상하좌우를 탐색하여 연합을 만든다. 연합은 시작 칸과 인접한 칸에서만 이루어지는게 아니라, 연합이 이루어진 칸에서도 인접한 칸을 비교하여 조건에 맞으면 연합이 이루어진다. 그러므로 각 칸을 bfs로 탐색하면서 연합을 이루는 칸이 어느 칸인지 탐색한다. 연합 벡터의 수가 2이상이라면, 인구 이동이 가능한 상태이므로 인구 이동을 실시한다. 이를..
문제 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 구현, 시뮬레이션 주사위의 각 면을 나눠서 생각하고, 현재 주사위의 아래쪽(D), 오른쪽(R), 앞쪽(F)에 해당하는 주사위 면을 설정하여 해결하였다. 각 면의 인덱스를 0, 1, 2, 3, 4, 5라고 하면 처음 상태에서 D는 0, R은 2, F는 4이다. 주사위를 4방향으로 움직이면 D, R, F는 밑의 코드처럼 변한다. // 주사위를 4방향으로 굴렸을 때, 아래, 오른쪽, 앞쪽의 주..
문제 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 구현, 브루트포스 알고리즘, 백트래킹 문제를 잘 읽어야 한다. 회전의 순서가 고정적인 것이 아니라, 배열의 최솟값을 구할 수 있도록 회전의 순서를 바꿀 수 있다. 회전의 순서를 정할 수 있도록, dfs를 이용하여 순열 알고리즘을 구현한다. // dfs를 이용한 순열 void dfs(bool select[], int map[], int cnt, int n, int k, vector v) { if (cnt == k) { sol..
문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 너비 우선 탐색, 구현, 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 문제의 2차원 배열에서 각 섬은 너비 우선 탐색으로 섬의 수와 위치를 파악할 수 있다. 배열에 섬의 위치와 섬의 번호를 설정하였다면, 섬과 섬 사이의 간선의 길이를 파악해야 한다. 섬의 모든 점에서 부터 상하좌우로 움직이며 다른 섬에 도달하였을 경우 거리를 파악하여 간선으로 vector에 넣는다. 점의 수가 최대 100이므로 시간초과는 발생하지 않는다. 해당 ..
문제 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 구현, 시뮬레이션, 큐 문제이다. 뱀의 머리, 꼬리, 몸통의 정보를 따로 저장해둔다. pair head = make_pair(0, 0); // 현재 머리의 위치 pair tail = make_pair(0, 0); // 현재 꼬리의 위치 queue body; // 사과를 먹지 못했을 때, 줄어들 꼬리의 위치가 front snake[0][0] = true; // 뱀이 있는 영역을 표시 이동 후 머리의 위치를 queue에 넣어둔다. 이동 후 사과를 먹지 못했다면,..
문제 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 풀이 구현, 시뮬레이션 문제이다. 로봇 청소기가 후진하지 못할 때까지 while로 무한 루프를 돈다. 현재 위치의 상하좌우에 청소 가능한 칸이 있는지 확인한다. 북, 동, 남, 서 방향으로 이동할 때의 x, y의 위치 변화는 다음과 같다. // 북, 동, 남, 서 int move_x[4] = { -1, 0, 1, 0 }; int move_y[4] = { 0, 1, 0, -1 }; 청소 가능한 칸이 있다면 반시..
문제 풀이 구현, 시뮬레이션 문제이다. 원판을 2차원 배열로 생각하고 처리한다. 원판을 회전시킬 때, 끝과 처음이 연결되어 있는걸 주의해야 한다. 원판과 인접한 수를 탐색할 때, BFS로 인접한 수가 현재 수와 같은 원판의 위치를 탐색한다. 탐색의 결과로 수를 지울지, 평균을 구할지를 결정한다. 코드 #include #include #include #include using namespace std; typedef struct { int x; int y; }type; queue bfs; int circles[51][51]; bool visited[51][51]; int move_x[4] = { 0, 0, 1, -1 }; int move_y[4] = { 1, -1, 0, 0 }; int main() { i..
문제 풀이 백트래킹을 이용한, 구현, 시뮬레이션, 완전 탐색 문제이다. 궁수 3명을 배치하는데는 백트래킹을 사용한다. 배치를 완료하면 게임을 시작한다. 턴마다 적이 아래로 이동하는 것 보다, 궁수가 위로 이동하는 것이 더 간단하다. 각 궁수가 공격할 3명의 적을 탐색한다. 판을 하나하나 검사하면서 적일 경우 현재 궁수와의 거리를 측정한다. 현재까지 검색한 궁수와의 최소 거리보다 현재 측정한 거리가 더 가깝다면 타겟을 변경한다. 같다면 타겟들의 y값을 비교하여 더 작은 y값을 가진 타겟을 선택한다. 선택된 적은 중복되면 안 되므로 set에 저장된다. 선택된 타겟들을 공격하고 현재까지 처치한 적을 갱신한다. 궁수줄을 한 칸 위로 이동한다. 코드 #include #include #include #include..
문제 풀이 구현 문제다. 경사로를 놓을 수 없는 경우는 다음과 같다. 이전 칸과의 높이차가 2 이상인 경우 경사로를 놓을 칸의 높이가 서로 일치하지 않는 경우 경사로를 놓을 칸에 이미 경사로가 설치된 경우 경사로를 놓았을 때, 길의 범위를 벗어난 경우 문제의 답의 최댓값은 2 * N이다. 현재 검사하는 행 또는 열이 위의 4가지중 하나의 경우라면 답을 1차감한다. 코드 #include #include #include #include using namespace std; int nums1[101][101]; int nums2[101][101]; bool block[101][101]; int N, L; int answer; void solution(int nums[][101]) { for (int x = 0..
문제 풀이 구현, 시뮬레이션, 너비 우선 탐색, 그래프 탐색 문제이다. 터질 뿌요들을 탐색할 때, BFS를 이용한다. 상하좌우로 같은 색상의 뿌요들을 탐색했을 때, BFS 탐색의 횟수가 4이상이라면 터질 뿌요들이다. 이 것을 queue explode의 형태로 저장한다. explode 큐를 꺼내면서 뿌요를 터트린다. 터진 뿌요에 해당하는 필드는 '.'으로 값이 변한다. 밑에 빈 공간이 있는 뿌요들은 아래로 떨어져야 한다. 아랫줄부터 검사하면서 현재 검사하는 타일의 값이 '.'일 경우, 해당 타일 바로 위에 있는 뿌요 타일과 값을 바꾼다. 다시 explode 큐를 채우기 위해 BFS로 터질 뿌요들을 탐색하고, explode가 모두 비워질 때까지 반복한다. 코드 #include #include #include..
