본문 바로가기

Programming

BOJ 4179 · 불! 알고리즘 분류 : BFS불이 도달하기 전에 탈출하는 최단 거리를 구하는 문제다. BOJ 5427번 문제 '불'과 유사하다.불의 좌표를 먼저 큐에 집어 넣는다. 여러 곳이 있을 수 있으며, 모두 먼저 넣어야 한다.불 좌표를 모두 넣었다면, 이후에 사람 좌표를 넣는다.BFS 탐색 시작.C++ 소스코드#include <cstdio> #include <queue> using namespace std; struct fire { ..
BOJ 14503 · 로봇 청소기 알고리즘 분류 : 시뮬레이션로봇이 청소할 수 있는 영역의 최대 개수를 구하는 문제다. 문제의 조건을 그대로 구현하면 된다.방향은 북(0), 동(1), 남(2), 서(3) 순서로 둔다.로봇은 왼쪽으로만 돌기 때문에, 북(0)→서(3), 동(1)→북(0), 남(2)→동(1), 서(3)→남(2)으로 방향이 바뀐다.따라서 방향 전환은 (다음 방향) = (현재 방향 + 3) % 4 로 나타낼 수 있다.입력에서 청소되지 않은 칸은 (0), 벽은 (1)로 주어지..
BOJ 1726 · 로봇 알고리즘 분류 : BFS로봇이 출발 지점에서 도착 지점까지 이동하기 위해 필요한 최소 명령 횟수를 구하는 문제다. BFS를 통해 최단 거리를 구하는 문제인데, 방향 전환 명령과 이동 명령이 구분되어 있어서 까다롭다. 이동 명령을 먼저 내리고, 그다음에 방향 전환 명령을 내리는 흐름으로 짜야 한다.Queue에는 3가지 정보를 넣어야 한다. 그 정보는 'x좌표, y좌표, 현재 방향'이다.방문 여부를 확인하고, 명령 횟수를 저장할 배열 ..
BOJ 1600 · 말이 되고픈 원숭이 알고리즘 분류 : BFS원숭이가 시작 지점(0, 0)에서 도착 지점(H-1, W-1)까지 이동하는데 걸리는 최단 거리를 구하는 문제다. 전형적인 BFS 문제이지만, 이동하는 방법이 조금 다르다. 14442번 '벽 부수고 이동하기 2'와 7562번 '나이트의 이동'에서 써먹은 테크닉을 적절히 사용하면 해결할 수 있다.방문 체크와 이동 거리를 저장할 dist 배열을 3차원으로 선언한다.dist 배열의 인덱스는 [x 좌표] [y 좌표] [말 점프 횟수] ..
BOJ 7562 · 나이트의 이동 알고리즘 분류 : BFS나이트의 최단 이동 거리를 구하는 문제다. 전형적인 BFS 문제이며, 나이트 이동에 해당하는 이동 좌표만 잘 설정하면 된다.C++ 소스코드#include <cstdio> #include <cstring> #include <queue> using namespace std; struct chess { int x, y; }; int n, sx, sy, ex, ey; int d[300][30..
BOJ 2174 · 로봇 시뮬레이션 알고리즘 분류 : 시뮬레이션로봇의 움직임을 그대로 구현하는 문제다. 문제의 조건을 그대로 구현하면 된다. 동서남북의 방향과 회전의 방향에만 유의하면 큰 어려움은 없다.아래 코드에서는 다음과 같이 구현하였다.로봇의 번호가 적혀있는 맵을 가로(A)*세로(B) 사이즈로 만들어둔다.로봇의 좌표 위치와 회전 방향이 적혀있는 배열을 로봇의 개수(N) 만큼 만들어둔다.남동북서 순서로 인덱스를 매긴다. S(0), E(1), N(2), W(3)왼쪽 회전 : ..
BOJ 1194 · 달이 차오른다, 가자. 알고리즘 분류 : BFS미로를 탈출하는데 걸리는 최단 거리를 구하는 문제다. 전형적인 BFS 문제인데, 열쇠 조건이 약간 까다롭다. 열쇠는 소문자 a~f로 총 6가지 종류가 있으며, 문도 마찬가지로 대문자 A~F 6종류가 있다. 열쇠가 없으면 해당 알파벳에 상응하는 문을 열 수 없어서 통과할 수 없다. 열쇠 조건을 만족하면서 방문 여부를 체크하기 위해 3차원 배열을 선언할 필요가 있다.방문 여부 체크와 이동 거리를 저장할 배열 'd..
BOJ 1094 · 막대기 알고리즘 분류 : 시뮬레이션문제에 주어진 조건을 그대로 구현하는 문제다. X 길이를 만들기 위해 막대기를 자르고 이어붙인다. 막대기의 길이는 64부터 시작한다. 자르고 이어붙이는 방법은 우선 막대기의 총 길이 합이 X보다 크면, 반으로 자른다. 만약 반으로 자른 것 중 하나를 제외하고 더한 길이의 합이 X보다 크거나 같으면, 제외한 절반의 막대기를 버린다. 남은 막대기를 모두 더한 길이의 합이 X가 되지 않는다면 위 방법을 반복한다.이 문제..
BOJ 2460 · 지능형 기차 2 알고리즘 분류 : 시뮬레이션2455번 '지능형 기차' 문제에서 기차역 수를 10개로 늘린 문제다. 반복 횟수를 4에서 10으로만 바꿔서 해결할 수 있다.C++ 소스코드#include <cstdio> int main() { int ans = 0, sum = 0; for (int i=0; i<10; i++) { int x, y; scanf("%d %d", &x, &y); ..
BOJ 2455 · 지능형 기차 알고리즘 분류 : 시뮬레이션기차에 탄 사람이 가장 많을 때를 구하는 간단한 문제다. 각 기차역에서 탄 사람 수에 내린 사람 수를 빼고, 이를 더하면서 역마다 비교하면 된다.C++ 소스코드#include <cstdio> int main() { int ans = 0, sum = 0; for (int i=0; i<4; i++) { int x, y; scanf("%d %d", &x..
BOJ 3987 · 보이저 1호 알고리즘 분류 : 시뮬레이션보이저 1호가 시그널을 보내서 탐사할 수 있는 최대 거리를 출력하는 문제다. 문제에 주어진 조건을 그대로 구현하면 된다. 방향 처리는 숫자로 처리하면 간단하다.방향을 상(U), 우(R), 하(D), 좌(L) 순서로 만든다.U, R, D, L의 인덱스를 0, 1, 2, 3으로 둔다.입력받을 때, 가장자리를 모두 블랙홀('C')로 만들어두면 범위 밖을 처리하기 쉽다.'/'를 만났을 경우, 0 → 1, 1 → 0, 2 → 3, ..
BOJ 5213 · 과외맨 알고리즘 분류 : BFSBFS를 통해 최단 거리를 구하는 문제다. 일반적인 BFS 문제와 다르게, 주어지는 입력 데이터가 굉장히 골치 아프다. 입력 데이터를 인접 행렬로 적절하게 변환하는 과정이 필요하다.우선 주어지는 입력 데이터를 2차원 인접 행렬로 변환한다. 하나의 타일은 2 조각으로 나누어져 있으므로, 세로 N개 가로 N*2개이다. 따라서 인접 행렬을 a[N][N*2]로 선언한다.입력 데이터를 인접 행렬에 넣을 때, 홀수 줄,..