최대 반복 횟수는 1000, 체스판의 최대 크기는 12x12, 말의 최대 개수는 10이므로 탐색에만 약 1000만 번의 연산이 필요하다.
따라서 각 반복별로 말의 이동을 처리하는 기능을 위해 O(n)의 시간만 추가로 사용할 수 있을 것이다.
[ 풀이 방법 ]
1. 말을 순서대로 이동시키는 기능
- 1~K
- 말의 이동방향을 저장해 사용할 수 있어야 한다.
-> vector를 이용해 말의 좌표와 이동 방향을 저장하는 구조체를 저장하고, 말의 순서는 index로 처리
2. 말이 이동하려는 체스판의 칸 색깔에 따라 이동을 다르게 처리하는 기능
1. 흰색:
- 말을 이동시킨다.
- 이동하려는 칸에 이미 말이 있을 경우 가장 위에 올려놓는다.
- 말의 위에 다른 말들이 올려져 있을 경우, 말의 위에 있는 말들도 함께 이동한다.
2. 빨간색:
- 말의 이동 기능은 흰색과 동일하나, 이동하기 전에 말들이 올려진 순서를 반대로 바꾼다.
3. 파란색:
- 이동 방향을 반대로 돌린다.
- 방향 바꾼 뒤 이동해야 할 칸이 파란색이면 이동하지 않는다.
- 그 외의 경우 이동해야 할 칸의 색깔에 따라 말의 이동을 처리한다.
3. 말이 4마리 쌓이거나, 반복횟수가 1000을 넘을 때까지 위 과정을 반복한다.
체스판의 각 칸에 말을 추가하거나 일부의 말을 제거하는 기능, 말 n마리의 순서를 reverse하는 기능이 O(n)의 시간복잡도를 가지도록 구현해야 한다.
=> C++ string의 +연산자와 substr함수, STL의 reverse함수를 이용해 O(n) 시간복잡도를 가지도록 기능들을 구현할 수 있다. 따라서 각 칸에 위치한 말을 순서대로 저장하고 이동 기능을 처리하기 위해 string 자료형을 이용하였다.
[ 회고 ]
말의 이동 기능을 구현할 때, 체스판의 각 칸에 위치한 말과 말의 순서는 업데이트 하였으나 말들의 좌표와 방향을 저장하는 구조체의 배열은 업데이트하지 않아 기능이 올바르게 작동하지 않았다.
이 문제의 경우 예제 입력이 충분히 제공되어 디버깅을 통해 빠르게 문제의 원인을 찾고 해결할 수 있었지만, 예제 입력이 없었다면 시간이 오래 걸리거나 아예 찾지 못할 수 있었을 것이다.
앞으로 하나의 객체 정보를 담는 컨테이너가 여러개 필요한 문제가 주어진 경우, 빠뜨리지 말고 모든 객체 정보를 업데이트 해야한다는 것을 유의해야 할 것이다.
[ 정답 코드 ]
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define MAX 12
#define WHITE 0
#define RED 1
#define BLUE 2
using namespace std;
struct Horse {
int r; int c;
int dir;
};
int N, K;
vector<vector<int>> colors;
string board[MAX][MAX];
vector<Horse> horse;
int res;
bool flag = false;
int dirR[4] = {0, 0, -1, 1};
int dirC[4] = {1, -1, 0, 0};
void move() {
for(int i = 0; i < horse.size(); i++) {
int k = i;
int r = horse[i].r;
int c = horse[i].c;
int dir = horse[i].dir;
int nr = r + dirR[dir];
int nc = c + dirC[dir];
int color;
if(nr < 0 || nr >= N || nc < 0 || nc >= N) color = BLUE;
else color = colors[nr][nc];
if(color == WHITE) {
auto it = board[r][c].find(to_string(k));
string movingHorse = board[r][c].substr(it);
board[r][c] = board[r][c].substr(0, it);
board[nr][nc] += movingHorse;
} else if(color == RED) {
auto it = board[r][c].find(to_string(k));
string movingHorse = board[r][c].substr(it);
reverse(movingHorse.begin(), movingHorse.end());
board[r][c] = board[r][c].substr(0, it);
board[nr][nc] += movingHorse;
} else if(color == BLUE) {
if(dir == 0 || dir == 2) dir += 1;
else dir = (dir+3)%4;
horse[k].dir = dir;
nr = r + dirR[dir];
nc = c + dirC[dir];
int color;
if(nr < 0 || nr >= N || nc < 0 || nc >= N) color = BLUE;
else color = colors[nr][nc];
if(color == WHITE) {
auto it = board[r][c].find(to_string(k));
string movingHorse = board[r][c].substr(it);
board[r][c] = board[r][c].substr(0, it);
board[nr][nc] += movingHorse;
} else if(color == RED) {
auto it = board[r][c].find(to_string(k));
string movingHorse = board[r][c].substr(it);
reverse(movingHorse.begin(), movingHorse.end());
board[r][c] = board[r][c].substr(0, it);
board[nr][nc] += movingHorse;
} else if(color == BLUE) {
nr = r;
nc = c;
}
}
if(board[nr][nc].length() >= 4) {
flag = true;
return;
}
for(int j = 0; j < board[nr][nc].length(); j++) {
int k = (board[nr][nc][j] - '0');
horse[k].r = nr;
horse[k].c = nc;
}
}
}
void solve() {
while(res <= 1000) {
if(flag) break;
move();
res++;
}
}
int main() {
iostream::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
colors.resize(N, vector<int>(N));
for(int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> colors[i][j];
}
}
for(int k = 0; k < K; k++) {
int r, c, d;
cin >> r >> c >> d;
horse.push_back({r-1, c-1, d-1});
board[r-1][c-1] += to_string(k);
}
solve();
if(res > 1000) cout << -1 << '\n';
else cout << res << '\n';
return 0;
}
'알고리즘 문제 풀이 > BOJ' 카테고리의 다른 글
[ BOJ - 6549번 ] 히스토그램에서 가장 큰 직사각형 (C++) (0) | 2024.01.17 |
---|---|
[ BOJ - 17822번 ] 원판 돌리기 (C++) (0) | 2024.01.17 |
[ BOJ - 2042번 ] 구간 합 구하기 (C++) (1) | 2024.01.15 |
[ BOJ - 17779번 ] 게리멘더링 2 (C++) (0) | 2024.01.15 |
[ BOJ - 1753번 ] 최단 경로 (C++) (0) | 2024.01.13 |