BOJ
BOJ 17086 · 아기 상어 2
알고리즘 분류 : BFS 아기 상어와의 거리를 구하는 문제다. BOJ 17086번 아기 상어와는 완전히 다른 문제다. 각 좌표에서 아기 상어와 떨어진 거리가 안전거리이며, 안전거리의 최댓값을 구해야 한다. 맵을 입력받으면서 상어의 위치(1)가 주어지면, 큐에 모두 집어넣는다.각 상어 위치부터 BFS 탐색을 하면서, 빈칸(0)이면 이동하면서 이동거리를 맵에 저장한다.맵을 완전 탐색한 후, 맵에 저장된 최댓값이 안전거리의 최댓값이 된다.거리를 1부터 시작했기 때문에, 정답은 위에서 구한 최댓값에 1을 빼야 한다. ✓ 1번 예제 테스트케이스를 설명하는 그림이다. 각 상어 위치(초록색)부터 BFS를 시작하면, 오른쪽 상태처럼 된다. C++ 소스코드 #include #include using namespace s..
BOJ 5373 · 큐빙
알고리즘 분류 : 시뮬레이션 루믹스 큐브의 회전을 주어진 조건 그대로 구현하는 문제다. 큐브의 좌표를 적당히 설정해서 회전하면 된다. 번뜩이는 아이디어가 떠오르지 않아서 무식하게 구현했다. 배열 인덱스가 꼬이기 십상인지라, 상당히 번거롭고 귀찮은 문제다. 큐브를 적당히 고정해놓고 좌표를 설정한다.각 면에 인덱스를 0~5까지 붙였다.3차원 배열 cube의 인덱스는 [면 번호] [서브 사각형 X좌표] [서브 사각형 Y좌표] 이다.각 면은 3*3의 서브 사각형으로 이루어져 있으며, 각 좌표는 (0,0)부터 (2,2)까지이다.아래 그림에서 각 면에 있는 검은색 점은 (0,0)의 위치다.각 면을 정면으로 바라보는 기준으로 회전을 시키면서 좌표의 변화를 업데이트해야 한다. C++ 소스코드 #include int n..
BOJ 15685 · 드래곤 커브
알고리즘 분류 : 시뮬레이션 문제에 주어진 조건 그대로 드래곤 커브를 만들어서 사각형의 개수를 세는 문제다. 드래곤 커브를 만드는 규칙을 파악해야 한다. 드래곤 커브는 최대 10세대까지 있으며, 일정한 규칙에 따라 만들어진다.1. N세대 드래곤 커브를 만든다고 가정하자.2. N-1세대 드래곤 커브를 우선 복사하고, 이것을 시계 방향으로 90도 회전시킨다.3. 회전 시킨 드래곤 커브를 N-1세대 드래곤 커브의 마지막에 이어 붙인다.위 1~3 과정을 10세대까지 반복하면 된다. 쉽게 구현하기 위해서, 드래곤 커브를 좌표 대신 방향을 사용한다.방향은 0(→) 1(↑) 2(←) 3(↓) 이다.첫 출발 방향을 0으로 둔다.이전 세대의 마지막 방향에서 출발 방향까지 거꾸로 탐색하면서, 각 방향에 1을 더하고 이어 ..
BOJ 14500 · 테트로미노
알고리즘 분류 : 브루트 포스 테트로미노를 N*M 종이 맵에 하나 두었을 때, 얻을 수 있는 합의 최대를 구해야 한다. 테트로미노란 정사각형 4개를 이어붙인 도형이다. 문제에 주어진 5개의 테트로미노는 각각 회전, 대칭이 가능하다. 회전, 대칭을 모두 고려하면, 서로 다른 모양의 도형을 총 19가지 만들 수 있다. 19가지의 도형을 모두 만든다.각 도형에서 하나의 사각형을 중심으로 인덱스를 설정한다. (그림 참조)각 도형 중에 하나를 맵에 두고 합을 구한다.가장 큰 합이 정답이다. C++ 소스코드 #include int n, m, ans; int a[500][500]; const int b[19][4][2] = { { {0,0}, {0,1}, {1,0}, {1,1} }, // ㅁ { {0,0}, {0,1..
BOJ 15686 · 치킨 배달
알고리즘 분류 : 브루트 포스 집과 치킨집과의 거리를 각각 구해서 최소의 치킨 거리를 구하는 문제다. 여러 개의 치킨 집에서 M개의 치킨 집을 고른 후, 문제에 주어진 조건대로 치킨 거리를 구해서 답을 찾아야 한다. 입력받을 때, 치킨집(2)의 개수와 집(1)의 개수를 세고, 각 좌표 (X, Y)를 리스트에 저장한다.치킨집의 총 개수를 K개라고 할 때, 재귀 함수를 통해 K개 중 M개를 골라야 한다. 조합 방식으로 고르면 된다.M개의 치킨집을 모두 고르면, 집과 치킨집과의 치킨거리를 구하고, 그중 최솟값을 정답으로 한다. C++ 소스코드 #include #include #include using namespace std; struct pos { int x, y; }; int n, m, ans=1e9; v..
BOJ 15684 · 사다리 조작
알고리즘 분류 : 브루트 포스, 백트래킹 사다리를 적절히 만들어서 사다리 타기를 해야하는 문제다. 가로줄은 최대 3개까지 놓을 수 있고, 최솟값을 출력하면 된다. 출발한 사다리 번호(세로줄)와 도착한 사다리 번호가 모두 같아야 사다리를 제대로 탄 것이다. 가능한 사다리를 모두 만들면 시간 초과될 수 있으므로, 적절히 백트래킹을 하여 경우의 수를 줄여야 한다. 주어진 입력을 통하여 H*N 사이즈의 사다리를 만든다.A번 세로줄과 A+1번 세로줄의 사이에 B번 가로줄로 연결한다면, 사다리 [A][B]를 연결(1)한다.아래 그림을 확인. 재귀 함수를 이용하여 가능한 사다리를 만든다.사다리에 가로줄을 만들 때, 가로줄은 연속해서 만들지 않아도 되는 것에 유의한다.만약 현재 위치가 (i, j)이고, 사다리가 연결되..
BOJ 14890 · 경사로
알고리즘 분류 : 시뮬레이션 경사로를 만들어서 지나갈 수 있는 길의 개수를 구하는 문제다. 문제에 주어진 조건에 따라 그대로 구현해야 한다. 지나갈 수 있는 길을 확인하기 위해 가로 방향과 세로 방향을 구분해서 순차 탐색해야 한다.먼저 현재 칸의 높이 A와 다음 칸의 높이 B를 구하고, B-A를 D라고 하자.D가 0이라면, 길의 높이가 같은 경우이다.D가 1이라면, 올라가는 경사로가 필요한 경우이다.D가 -1이라면, 내려가는 경사로가 필요한 경우이다. 길의 높이가 같다면 (D == 0), 카운트를 1 증가시킨다. 카운트는 경사로의 길이와 비교하기 위해 필요하다.올라가는 경사로라면 (D == 1), 카운트가 경사로의 길이 L 이상인지 확인한다. 카운트가 L 이상이라면, 경사로를 놓을 수 있는 경우이므로, ..
BOJ 15662 · 톱니바퀴 (2)
알고리즘 분류 : 시뮬레이션 T개의 톱니바퀴를 회전시키는 시뮬레이션 문제다. BOJ 14891번 '톱니바퀴'와 유사한 문제이다. 자세한 내용은 이전 문제 참조. 톱니바퀴의 수는 T개이다. 최대 1,000개.정답은 12시 방향에 S극(1)이 몇 개 있는지만 세면 된다. C++ 소스코드 #include int a[1000][8]; int t, k, ans; void rotate(int n, int d) { int t[8]; if (d == 1) { for (int i=0; i