문제 설명: 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다. 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다. "0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 반환하는 함수를 작성
입력
board의 한 변의 길이는 5 이상 100 이하
로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어짐
로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어짐
출력: 최소 시간
풀이
로봇을 상하좌우로 이동하거나 회전하는 경우 1초가 지나기 때문에 로봇의 위치를 노드로 저장해서 BFS로 구현
로봇의 두 좌표 중 하나라도 (N, N)에 도달하면 그 때 걸린 시간이 최소 시간
로봇의 위치를 어떻게 나타낼 것인가? 두 좌표 중 1개(x,y)와 그 좌표에서 다음 좌표를 가리키는 방향(상/하/좌/우 총 4가지)
두 좌표를 저장하는 것보다 회전/이동이 쉽고 방문 체크나 벽 체크하기 용이함
로봇의 좌표를 c1과 c2라고 할 때 방향(dir)에 따라 좌표는 아래와 같음
좌표의 변화? (dir 은 d배열의 인덱스)
움직이는 경우 => c1 에만 변화를 주고 dir은 그대로
회전하는 경우 => c1, c2 각각에 대해 다음과 같이 2가지 종류로 회전
dir=0,2 이면 dir=1,3 으로 호출
dir=1,3 이면 dir=0,2 으로 호출
회전한 후의 좌표를 (ny,nx)라 할 때 돌리는 방향에 벽이 없어야 함
dir=0,2
c1이 축이면 (ny, c2.X) 와 회전 후 좌표 모두 벽이 아니고 범위 안에 있어야 함
c2가 축이면 (ny, c1.X) 와 회전 후 좌표 모두 벽이 아니고 범위 안에 있어야 함
dir=1,3
c1이 축이면 (c2.Y, nx) 와 회전 후 좌표 모두 벽이 아니고 범위 안에 있어야 함
c2가 축이면 (c1.Y, nx) 와 회전 후 좌표 모두 벽이 아니고 범위 안에 있어야 함
정답 코드
#include <string>
#include <vector>
#include <queue>
#include <cstring>
#define Y first
#define X second
using namespace std;
typedef pair<int,int> pii;
const int d[5] = {0, -1, 0, 1, 0};
vector<vector<int>> B;
int N;
bool isInRange(pii c) {
if (c.Y < 0 or c.Y >= N or c.X < 0 or c.X >= N) return false;
return !B[c.Y][c.X];
}
int bfs() {
int ret = 0;
bool visited[100][100][4];
memset(visited, 0, sizeof(visited));
queue<pair<int, pii>> q; // (dir, (y,x))
q.push({2, {0,0}});
visited[0][0][2] = true;
while (!q.empty()) {
int sz = q.size();
while (sz--) { // depth 계산을 정확하게 하기 위해 딱 존재하는 노드만큼만 수행
int dir = q.front().first;
pii c1 = q.front().second;
pii c2 = {c1.Y + d[dir], c1.X + d[dir+1]};
q.pop();
if ((c1.Y == N-1 and c1.X == N-1) or (c2.Y == N-1 and c2.X == N-1))
return ret;
// 상하좌우 이동: (y,x)만 변화를 주고 dir은 그대로 유지
for (int i = 0; i < 4; i++) {
pii nc1 = {c1.Y + d[i], c1.X + d[i+1]};
pii nc2 = {nc1.Y + d[dir], nc1.X + d[dir+1]};
if (isInRange(nc1) and isInRange(nc2) and !visited[nc1.Y][nc1.X][dir]) {
q.push({dir, nc1});
visited[nc1.Y][nc1.X][dir] = true;
}
}
// 회전: dir에 따라 회전할 방향과 좌표 검사를 함
int newDir[2] = {(dir&1) ? 0 : 1, (dir&1) ? 2 : 3};
for (int i = 0; i < 2; i++) {
int rd = newDir[i];
pii nc2 = {c1.Y + d[rd], c1.X + d[rd+1]};
// c1 을 축으로 회전
if (isInRange(nc2)) {
if (((dir & 1) and isInRange({c2.Y, nc2.X})) or
(!(dir & 1) and isInRange({nc2.Y, c2.X}))) {
if (!visited[c1.Y][c1.X][rd]) {
q.push({rd, c1});
visited[c1.Y][c1.X][rd] = true;
}
}
}
// c2 를 축으로 회전
pii nc1 = {c2.Y + d[rd], c2.X + d[rd+1]};
if (isInRange(nc1)) {
if (((dir & 1) and isInRange({c1.Y, nc1.X})) or
(!(dir & 1) and isInRange({nc1.Y, c1.X}))) {
if (!visited[c2.Y][c2.X][rd]) {
q.push({rd, c2});
visited[c2.Y][c2.X][rd] = true;
}
}
}
}
}
ret++;
}
return ret;
}
int solution(vector<vector<int>> board) {
N = board.size();
B = board;
return bfs();
}
문제 설명: 레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있어 친구들을 보내 점검하고자 한다. 빠른 공사를 위해 점검 시간을 1시간으로 제한했다. 외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 반환하는 함수를 작성
레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리
친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동
입력
n은 1 이상 200 이하인 자연수
weak의 길이는 1 이상 15 이하
취약 지점의 위치는 오름차순으로 정렬
weak의 원소는 0 이상 n - 1 이하인 정수
dist의 길이는 1 이상 8 이하
dist의 원소는 1 이상 100 이하인 자연수
출력: 친구 수의 최솟값
친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 반환
n
weak
dist
result
12
[1, 5, 6, 10]
[1, 2, 3, 4]
2
12
[1, 3, 4, 9, 10]
[3, 5, 7]
1
풀이
dist 배열을 내림차순으로 정렬
각 친구마다 weak의 각 위치에 배치해보면서 시계방향, 반시계방향으로 점검하는 경우를 모두 시도해서 모든 취약 지점이 점검되는 경우 최소 친구 수를 탐색
dist 배열의 크기가 최대 8이고, weak 배열의 크기가 최대 15이기 때문에 매 취약 지점마다 각 친구를 배치하는 경우를 모두 탐색할 수 있다고 생각해서 완전 탐색으로 풀었는데 시간 초과 발생
현재 배치될 친구 인덱스와 점검한 weak 목록에 대해 부분 문제가 발생하므로 DP로 최적화
정답 코드
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int N;
const int INF = 1e9;
int dp[8][1<<15];
int dfs(int pos, vector<int>& dist, vector<int>& weak, int checked) {
// 모든 취약지점이 점검되었다면 0을 반환
if (__builtin_popcount(checked) == weak.size()) return 0;
if (pos == dist.size()) return INF; // 모든 친구가 배치되었으면 INF
int& ret = dp[pos][checked];
if (ret != -1) return ret;
ret = INF;
for (int i = 0; i < weak.size(); i++) {
if (checked & (1 << i)) continue;
// 시계 방향
int newChecked = checked;
int maxPos = weak[i] + dist[pos];
for (int j = i; ; j++) {
if (j == weak.size()) { // 끝에 도달한 경우 첫번째 취약 지점으로 인덱스 갱신
j = 0;
// 최대 이동 가능 지점도 갱신. 정북 지점을 지나지 않으면 -1
maxPos = weak[i] + dist[pos] > N ? maxPos % N : -1;
}
// 아직 점검되지 않았고 이동 반경 내에 있으면 점검
if (!(newChecked & (1 << j)) and weak[j] <= maxPos)
newChecked |= (1 << j);
else break;
}
ret = min(ret, dfs(pos+1, dist, weak, newChecked) + 1);
// 반시계 방향
newChecked = checked;
int minPos = weak[i] - dist[pos];
for (int j = i; ; j--) {
if (j < 0) { // 첫번째 지점에 도달한 경우 마지막 취약 지점으로 인덱스 갱신
j = weak.size()-1;
// 최대 이동 가능 지점도 갱신. 정북 지점을 지나지 않으면 N
minPos = weak[i] < dist[pos] ? minPos + N : N;
}
if (!(newChecked & (1 << j)) and weak[j] >= minPos)
newChecked |= (1 << j);
else break;
}
ret = min(ret, dfs(pos+1, dist, weak, newChecked) + 1);
}
return ret;
}
int solution(int n, vector<int> weak, vector<int> dist) {
N = n;
sort(dist.begin(), dist.end(), [&](int a, int b) mutable { return a > b; });
memset(dp, -1, sizeof(dp));
int ret = dfs(0, dist, weak, 0);
return ret == INF ? -1 : ret;
}
문제에서 정해진 규칙이 유지되는지 검사하는 함수(check)와 배열에 기둥/보를 설치 및 삭제하는 작업을 하는 함수(build)를 작성
기둥과 보 2가지 구조물만 가지므로 비트 연산으로 해당 위치에 구조물의 존재를 파악
설치할 때는 설치 위치에 대해서만 조건을 검사하면 되지만, 삭제할 때는 삭제 후 주변 구조물에 대해 조건을 만족하는지 검사해야 하므로 check함수를 여러 번 호출해주어야 함
작업별 조건
기둥 설치: 설치할 위치가 바닥/보 또는 왼쪽에 보 또는 아래에 기둥
보 설치: 설치할 위치에 기둥 또는 오른쪽에 기둥 또는 양쪽에 보
기둥 삭제: 삭제후 (x-1,y+1), (x,y+1) 위치에 있는 보/기둥에 대해 위의 조건들을 각각 검사
보 삭제: 삭제후 (x-1,y), (x+1,y)에 있는 보 또는 (x,y), (x+1,y)에 있는 기둥의 조건을 각각 검사
정답 코드
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> structure;
bool check(int y, int x, int build_type) {
bool ret = true; // 경계에 아무것도 없는 경우 삭제/설치 가능하므로 기본은 true
// 기둥 설치 또는 삭제 시 해당 위치에 기둥이 있으면
if ((structure[y][x] & 1) or build_type == 0) {
// 바닥이거나 아래에 기둥이 있거나, 양 끝에 보가 하나 있으면 true
if (y == 0 or (y > 0 and (structure[y-1][x] & 1)) or
(structure[y][x] & 2) or (x > 0 and (structure[y][x-1] & 2)))
ret = true;
else ret = false;
}
// 보 설치 또는 삭제 시 해당 위치에 보가 있으면
if ((structure[y][x] & 2) or build_type == 1) {
// 양 끝에 기둥이 하나 있거나, 양 끝 모두 보가 있으면 true
if ((structure[y-1][x] & 1) or (structure[y-1][x+1] & 1) or
(x > 0 and (structure[y][x-1] & 2) and (structure[y][x+1] & 2)))
ret = true;
else ret = false;
}
return ret;
}
void build(vector<vector<int>>& build_frame) {
for (auto& v : build_frame) {
int x = v[0], y = v[1], a = v[2];
if (v[3]) {
if (check(y, x, a))
structure[y][x] |= 1 << a;
} else {
structure[y][x] ^= 1 << a;
if (a == 0) { // 기둥 삭제 후 조건 검사
if (check(y+1, x, -1))
if (x == 0 or (x > 0 and check(y+1, x-1, -1)))
continue;
} else { // 보 삭제 후 조건 검사
if (check(y, x, -1) and check(y, x+1, -1))
if (x == 0 or (x > 0 and check(y, x-1, -1)))
continue;
}
structure[y][x] |= 1 << a;
}
}
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
vector<vector<int>> answer;
structure = vector<vector<int>> (n+2, vector<int> (n+2,0));
build(build_frame);
for (int x = 0; x < n+1; x++) {
for (int y = 0; y < n+1; y++) {
if (structure[y][x] & 1) answer.push_back({x, y, 0});
if (structure[y][x] & 2) answer.push_back({x, y, 1});
}
}
return answer;
}
