BOJ
BOJ 15664 · N과 M (10)
알고리즘 분류 : 브루트 포스 입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (6) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. 중복을 제거하는 방법은 N과 M (9) 문제와 동일하게 처리하면 된다. C++ 소스코드 #include #include #include #include using namespace std; int n, m; bool check[8]; int a[8]; vector v; set s; void solve(int cnt, int idx) { if (cnt == m) { s.insert(v); return; } for (int i=idx; i
BOJ 15663 · N과 M (9)
알고리즘 분류 : 브루트 포스 입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (5) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. 같은 숫자가 여러 개 주어질 수 있으므로, 해당 숫자가 총 몇 개 있는지 세어야 한다.먼저 N개의 숫자가 있는 리스트를 오름차순으로 정렬한다.숫자 리스트에서 처음부터 끝까지 순서대로 이동하면서 각 숫자가 몇 개 있는지 센다.숫자를 세는 방법은 아래와 같다.1. 현재 숫자가 이전 숫자와 같으면, 중복된 숫자이므로 현재 숫자의 개수를 1 증가시킨다.2. 현재 숫자가 이전 숫자와 다르면, 새로운 숫자이므로 숫자 카운트를 1로 둔다. 이전에 카운트한 숫자의 값을 저장한다. C++ 소스코드 #include #include #include us..
BOJ 4179 · 불!
알고리즘 분류 : BFS 불이 도달하기 전에 탈출하는 최단 거리를 구하는 문제다. BOJ 5427번 문제 '불'과 유사하다. 불의 좌표를 먼저 큐에 집어 넣는다. 여러 곳이 있을 수 있으며, 모두 먼저 넣어야 한다.불 좌표를 모두 넣었다면, 이후에 사람 좌표를 넣는다.BFS 탐색 시작. C++ 소스코드 #include #include using namespace std; struct fire { int x, y, f; }; int R, C, sx, sy; char a[1000][1000]; int dist[1000][1000]; queue q; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void bfs() { q.push({sx, sy, 0}); di..
BOJ 14503 · 로봇 청소기
알고리즘 분류 : 시뮬레이션 로봇이 청소할 수 있는 영역의 최대 개수를 구하는 문제다. 문제의 조건을 그대로 구현하면 된다. 방향은 북(0), 동(1), 남(2), 서(3) 순서로 둔다.로봇은 왼쪽으로만 돌기 때문에, 북(0)→서(3), 동(1)→북(0), 남(2)→동(1), 서(3)→남(2)으로 방향이 바뀐다.따라서 방향 전환은 (다음 방향) = (현재 방향 + 3) % 4 로 나타낼 수 있다.입력에서 청소되지 않은 칸은 (0), 벽은 (1)로 주어지므로, 이를 구분하기 위해 청소한 칸은 (2)로 바꾼다.1. 위에 주어진 데로 4번 회전을 하면서 청소가 가능한 칸이 있는지 확인한다.2. 청소할 수 있다면, 그 칸으로 전진하고 방향은 왔던 방향을 유지한다. 과정 1번부터 다시 반복한다.3. 한 칸도 청소..
BOJ 1726 · 로봇
알고리즘 분류 : BFS 로봇이 출발 지점에서 도착 지점까지 이동하기 위해 필요한 최소 명령 횟수를 구하는 문제다. BFS를 통해 최단 거리를 구하는 문제인데, 방향 전환 명령과 이동 명령이 구분되어 있어서 까다롭다. 이동 명령을 먼저 내리고, 그다음에 방향 전환 명령을 내리는 흐름으로 짜야 한다.Queue에는 3가지 정보를 넣어야 한다. 그 정보는 'x좌표, y좌표, 현재 방향'이다.방문 여부를 확인하고, 명령 횟수를 저장할 배열 'dist' 를 3차원 배열로 선언한다. 인덱스는 큐에 들어가는 정보와 같다.이동 명령은 1, 2, 3 거리로 이동할 수 있으므로, 1칸 이동부터 3칸 이동 순으로 진행한다.이동할 때 만약 앞에 벽이 있다면 곧바로 for 문을 break 한다. 짧은 거리를 못 가면, 더 긴 ..
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..