BOJ
BOJ 1194 · 달이 차오른다, 가자.
알고리즘 분류 : BFS 미로를 탈출하는데 걸리는 최단 거리를 구하는 문제다. 전형적인 BFS 문제인데, 열쇠 조건이 약간 까다롭다. 열쇠는 소문자 a~f로 총 6가지 종류가 있으며, 문도 마찬가지로 대문자 A~F 6종류가 있다. 열쇠가 없으면 해당 알파벳에 상응하는 문을 열 수 없어서 통과할 수 없다. 열쇠 조건을 만족하면서 방문 여부를 체크하기 위해 3차원 배열을 선언할 필요가 있다. 방문 여부 체크와 이동 거리를 저장할 배열 'dist'를 3차원으로 선언한다.dist 배열의 인덱스는 [x좌표] [y좌표] [보유 열쇠] 이다.보유 열쇠는 비트마스크를 사용한다.각 열쇠는 a(1
BOJ 1094 · 막대기
알고리즘 분류 : 시뮬레이션 문제에 주어진 조건을 그대로 구현하는 문제다. X 길이를 만들기 위해 막대기를 자르고 이어붙인다. 막대기의 길이는 64부터 시작한다. 자르고 이어붙이는 방법은 우선 막대기의 총 길이 합이 X보다 크면, 반으로 자른다. 만약 반으로 자른 것 중 하나를 제외하고 더한 길이의 합이 X보다 크거나 같으면, 제외한 절반의 막대기를 버린다. 남은 막대기를 모두 더한 길이의 합이 X가 되지 않는다면 위 방법을 반복한다. 이 문제는 2진수 방법으로도 해결할 수 있다.막대기는 64부터 시작하고, 막대기는 계속해서 절반으로 쪼개진다.즉, 64, 32, 16, 8, 4, 2, 1 순으로 쪼개진다.때문에 막대기 조각은 반드시 64, 32, 16, 8, 4, 2, 1의 조합으로 이루어져 있다.이 숫..
BOJ 2460 · 지능형 기차 2
알고리즘 분류 : 시뮬레이션 2455번 '지능형 기차' 문제에서 기차역 수를 10개로 늘린 문제다. 반복 횟수를 4에서 10으로만 바꿔서 해결할 수 있다. C++ 소스코드 #include int main() { int ans = 0, sum = 0; for (int i=0; i
BOJ 2455 · 지능형 기차
알고리즘 분류 : 시뮬레이션 기차에 탄 사람이 가장 많을 때를 구하는 간단한 문제다. 각 기차역에서 탄 사람 수에 내린 사람 수를 빼고, 이를 더하면서 역마다 비교하면 된다. C++ 소스코드 #include int main() { int ans = 0, sum = 0; for (int i=0; i
BOJ 3987 · 보이저 1호
알고리즘 분류 : 시뮬레이션 보이저 1호가 시그널을 보내서 탐사할 수 있는 최대 거리를 출력하는 문제다. 문제에 주어진 조건을 그대로 구현하면 된다. 방향 처리는 숫자로 처리하면 간단하다. 방향을 상(U), 우(R), 하(D), 좌(L) 순서로 만든다.U, R, D, L의 인덱스를 0, 1, 2, 3으로 둔다.입력받을 때, 가장자리를 모두 블랙홀('C')로 만들어두면 범위 밖을 처리하기 쉽다.'/'를 만났을 경우, 0 → 1, 1 → 0, 2 → 3, 3 → 2로 방향이 변한다.'\'를 만났을 경우, 0 → 3, 1 → 2, 2 → 1, 3 → 0으로 방향이 변한다.방향 전환은 배열의 인덱스와 값으로 처리하면 된다.주어진 시작점에서 4방향으로 돌리고, 이동은 무한 루프를 통해 구현한다.무한 루프를 돌면서..
BOJ 5213 · 과외맨
알고리즘 분류 : BFS BFS를 통해 최단 거리를 구하는 문제다. 일반적인 BFS 문제와 다르게, 주어지는 입력 데이터가 굉장히 골치 아프다. 입력 데이터를 인접 행렬로 적절하게 변환하는 과정이 필요하다.우선 주어지는 입력 데이터를 2차원 인접 행렬로 변환한다. 하나의 타일은 2 조각으로 나누어져 있으므로, 세로 N개 가로 N*2개이다. 따라서 인접 행렬을 a[N][N*2]로 선언한다.입력 데이터를 인접 행렬에 넣을 때, 홀수 줄, 짝수 줄에 따라 다르게 넣어야 한다. 홀수 줄에서는 2*N개의 데이터를 모두 넣는다. 짝수 줄에서는 앞뒤로 한 칸씩 0으로 비워놓고, 안쪽에 2*N-1개의 데이터를 넣는다. 데이터는 총 N*N-N/2줄에 2개씩 들어온다.인접 행렬을 만들면서 각 타일의 레벨 값을 저장할 배열..
BOJ 15683 · 감시
알고리즘 분류 : 브루트 포스 5종류의 CCTV를 키고 끄면서, CCTV가 감시할 수 없는 영역인 사각지대의 최소 크기를 맞추는 문제다. 최대 8개의 CCTV가 주어지고, 각 CCTV는 일정한 방향성을 가지고 있다. CCTV는 90도로 회전하며 사용할 수 있고, 이에 따라서 감시 영역이 바뀐다. 이 문제는 N이 최대 8이기 때문에, 모든 경우의 수를 구해서 최소 크기를 구하면 된다. CCTV 1~5번에 해당하는 방향을 만든다. 아래 코드에서는 비트 연산을 통해 만들었다.위쪽 방향 : 0001 == 1
BOJ 11559 · Puyo Puyo
알고리즘 분류 : BFS, 시뮬레이션 게임 '뿌요 뿌요'를 프로그래밍하는 문제다. 주어진 뿌요뿌요 판에서 얼마나 많은 연쇄가 일어나는지 맞춰야 한다. BFS를 통해 전체 탐색을 하고, 터트릴 수 있는 블록이 있는지 확인하면서, 4개 이상이면 터트리고 아래로 떨어뜨리면 된다. 1. 아래에서부터 블록(R,G,B,P,Y)을 확인한다. 빈 공간(.)은 무시한다.2. 블록을 발견하면, BFS 탐색을 통해 같은 색깔의 블록이 몇 개나 인접해있는지 확인한다.3. 만약 인접한 블록이 4개 이상이면, 서로 연결된 블록을 모두 터트린다. 터트린 블록은 빈 공간으로 만든다.4. 위쪽 끝까지 1~3 과정을 반복한다.5. 만약 블록이 한 번이라도 터졌다면, 정답 카운트를 1 증가시키고, 아래로 떨어질 수 있는 블록이 있는지 확..