프로그래밍
BOJ 1600 · 말이 되고픈 원숭이
알고리즘 분류 : BFS 원숭이가 시작 지점(0, 0)에서 도착 지점(H-1, W-1)까지 이동하는데 걸리는 최단 거리를 구하는 문제다. 전형적인 BFS 문제이지만, 이동하는 방법이 조금 다르다. 14442번 '벽 부수고 이동하기 2'와 7562번 '나이트의 이동'에서 써먹은 테크닉을 적절히 사용하면 해결할 수 있다. 방문 체크와 이동 거리를 저장할 dist 배열을 3차원으로 선언한다.dist 배열의 인덱스는 [x 좌표] [y 좌표] [말 점프 횟수] 이다.Queue에도 x 좌표, y 좌표, 말 점프 횟수를 집어넣는다.이동 방향을 정할 dx, dy 배열을 만든다.dx, dy의 배열 길이는 12이며, 앞에 4칸은 인접한 +1 이동이고, 뒤에 8칸은 말 점프 이동이다.다음 이동을 정하는 for 문에서 인덱스..
BOJ 7562 · 나이트의 이동
알고리즘 분류 : BFS 나이트의 최단 이동 거리를 구하는 문제다. 전형적인 BFS 문제이며, 나이트 이동에 해당하는 이동 좌표만 잘 설정하면 된다. C++ 소스코드 #include #include #include using namespace std; struct chess { int x, y; }; int n, sx, sy, ex, ey; int d[300][300]; const int dx[] = {2, 1, -1, -2, -2, -1, 1, 2}; const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; void bfs() { queue q; q.push({sx, sy}); while (!q.empty()) { int x = q.front().x, y = q.front()..
BOJ 2174 · 로봇 시뮬레이션
알고리즘 분류 : 시뮬레이션 로봇의 움직임을 그대로 구현하는 문제다. 문제의 조건을 그대로 구현하면 된다. 동서남북의 방향과 회전의 방향에만 유의하면 큰 어려움은 없다. 아래 코드에서는 다음과 같이 구현하였다.로봇의 번호가 적혀있는 맵을 가로(A)*세로(B) 사이즈로 만들어둔다.로봇의 좌표 위치와 회전 방향이 적혀있는 배열을 로봇의 개수(N) 만큼 만들어둔다.남동북서 순서로 인덱스를 매긴다. S(0), E(1), N(2), W(3)왼쪽 회전 : S(0)→E(1), E(1)→N(2), N(2)→W(3), W(3)→S(0) 오른쪽 회전 : S(0)→W(3), E(1)→S(0), N(2)→E(1), W(3)→N(2)회전은 나머지 연산을 하면 된다. 왼쪽 회전 : (인덱스+1)%4, 오른쪽 회전 : (인덱스+3..
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방향으로 돌리고, 이동은 무한 루프를 통해 구현한다.무한 루프를 돌면서..