풀이 방법은 문제에 다 주어진다
정말 풀이 방법은 문제에 다 주어진다. 문제를 놓치는 부분 없이 꼼꼼히 읽고, 어떤 함수를 만들지, 자료구조를 쓸지를 충분히 생각하고 들어가자. (범위도 조심)!!
이 단계에서 예외 case도 같이 생각해주면 금상첨화다 !!!!!
내일 파이팅하자 🍀
마법의 숲 탐색
상반기 코테 때, 도형이 실제 맵에 들어오기 전의 과정들을 단계별로 나누지 않아서 TC 1개를 통과 못했다..
다시는 같은 실수를 반복하지 말자. 문제에 답이 있다.
출구, 입구, 상황을 대비하여 mat에 전부 집어넣어줬다.
맵 한개로 모든 상황을 컨트롤 할 수 있다면 편리하다.
테트리스는 순간이동 하지 않는다. 내려오는 단계를 상세히 분석하자.
고대 문명 유적 탐사
3*3 만큼만 잘라서 회전하는 행렬을 생각해보자
//3*3 짤라서 돌리기 for (int i = 1; i <= 3; ++i) { for (int j = 1; j <= 3; ++j) { mat_copy[j][3 + 1 - i] = mat_tmp[i + (r - 2)][j + (c - 2)]; } } //적용 for (int i = 1; i <= 3; ++i) { for (int j = 1; j <= 3; ++j) { mat_tmp[i + (r - 2)][j + (c - 2)] = mat_copy[i][j]; } }r - 2, c - 2는 처음 돌릴 수 있는 행렬 중간 좌표이다.
시계방향으로 3*3 크기만큼 돌려주는 코드이다.
반시계 방향은 어떻게 될까??
//3*3 짤라서 돌리기
for (int i = 1; i <= 3; ++i) {
for (int j = 1; j <= 3; ++j) {
mat_copy[3 + 1 - j][i] = mat_tmp[i + (r - 2)][j + (c - 2)];
}
}
//적용
for (int i = 1; i <= 3; ++i) {
for (int j = 1; j <= 3; ++j) {
mat_tmp[i + (r - 2)][j + (c - 2)] = mat_copy[i][j];
}
}루돌플의 반란
각 단계를 함수로 나눠주어 debug 해가면서 풀자.
저번 준비 때 못풀었던 이유를 잊지말자.
priority_queue 와 vector sort에서 쓰이는 comp는 반대 역할을 한다.
연쇄적으로 밀리는 과정은 재귀로 처리하자.// 거리가 가까울수록, row가 클 수록, col이 클 수록 struct comp { bool operator()(const stru& a, const stru& b) { if (a.dis != b.dis) return a.dis > b.dis; if (a.r != b.r) return a.r < b.r; return a.c < b.c; } };위처럼 comp를 작성하여 pq에 사용한다면, dis가 작고, row값이 크고, col값이 큰 idx가 가장 위에 오게 된다. (pq 는 comp를 struct로 작성해야한다. 마지막에 ; 도 잊지말자.)
이번엔 vector에서 사용하는 comp를 생각해보자.bool comp (const stru& a, const stru& b) { if (a.dis != b.dis) return a.dis > b.dis; if (a.r != b.r) return a.r < b.r; return a.c < b.c; }sort(v.begin(), v.end(), comp)를 사용하면 dis가 크고, row값이 작고, col값이 작은 idx가 가장 처음에 오게 된다(v[0]).
WHY?
priority_queue는 default값이 max heap으로 되어있다. custom한 comp로 바꿔줬을 때, 우선순위를 어떤 idx가 받을지를 생각해보자. 또한, vector는 stack이고 pq는 말그대로 queue이다.
왕실의 기사 대결
테트리스와 비슷하다. 연쇄 작용은 recursive로 풀어주자.
⭐ 만약 TC가 틀리면 어떤 TC가 틀렸는지도 중요하지만, 해당 TC가 디버깅하기에 너무 크다면
문제 조건을 한번 더 봐보자. (역시 문제에 답이 있다.)
🍀예외 케이스를 생각하는 것은 정확한 풀이의 지름길이다.
메이즈 러너
범위를 정할 때 잔실수를 줄여야한다.
회전행렬 공식을 기억하자.
//회전 (빼놓고 돌리자..)
for (int i = 1; i <= ro_sz; ++i) {
for (int j = 1; j <= ro_sz; ++j) {
int mat_row = ro_r + i - 1;
int mat_col = ro_c + j - 1;
int tmp_row = j;
int tmp_col = ro_sz + 1 - i;
if (mat[mat_row][mat_col] != 0) {
tmp[tmp_row][tmp_col] = mat[mat_row][mat_col] - 1;
}
else {
tmp[tmp_row][tmp_col] = mat[mat_row][mat_col];
}
if (peo_idx[mat_row][mat_col].size()) {
visited[tmp_row][tmp_col] = 1;
v[tmp_row][tmp_col] = { mat_row, mat_col };
}
if (mat_row == exit_r && mat_col == exit_c) {
visited[tmp_row][tmp_col] = 2;
}
}
}
//적용해주기
for (int i = 1; i <= ro_sz; ++i) {
for (int j = 1; j <= ro_sz; ++j) {
int row = ro_r + i - 1;
int col = ro_c + j - 1;
if (visited[i][j] == 2) {
exit_r = row;
exit_c = col;
mat[row][col] = 0;
}
else {
mat[ro_r + i - 1][ro_c + j - 1] = tmp[i][j];
if (visited[i][j]) {
int cr = v[i][j].first;
int cc = v[i][j].second;
for (int idx = 0; idx < peo_idx[cr][cc].size(); ++idx) {
peo[peo_idx[cr][cc][idx]] = { row ,col };
}
}
}
}
}포탑 부수기
범위를 넘나들 수 있는 문제는 11 이 nn으로 넘어갈 수 있는지 여부를 반드시 확인하자.
bfs는 어차피 최단거리이다. 그리고 visited를 설정해놓는다면 1칸은 1번씩밖에 방문하지 않는다. 이 성질을 사용하면서 경로를 tracking 하기 위해 struct에 vector를 놓고 각각의 경로를 tracking 해주었다. (마지막에 pop_back 함으로써 계속해서 cv로 유지되게끔 해주었다.
📖같은 성질을 사용해서 각 칸의 back_x[nx][ny] 에 cr을 저장해주고 back_y[nx][ny]에 cy를 저장해주는 방법도 있다 !!//경로 tracking code vector<pair<int, int>> cv; while (!q.empty()) {
auto it = q.front();
int cr = it.row;
int cc = it.col;
cv = it.vec;
q.pop();
for (int i = 0; i < 4; ++i) {
int nr = cr + dx[i];
int nc = cc + dy[i];
//위로
if (nr == 0 && nc != 0) {
nr = n;
}
//아래로
else if (nr == n + 1 && nc != 0) {
nr = 1;
}
//우측
else if (nr != 0 && nc == m + 1) {
nc = 1;
}
//아래
else if (nr != 0 && nc == 0) {
nc = m;
}
if (visited[nr][nc] || mat[nr][nc] == 0) { continue; }
if (nr == dest_r && nc == dest_c) {
fg = 1;
v = cv;
break;
}
cv.push_back({ nr, nc });
//defense 도착
q.push({ nr, nc, cv });
cv.pop_back();
visited[nr][nc] = 1;
}
if (fg == 1) { break; }
}
//범위 코드
//위로
if (nr == 0) {
nr = n;
}
//아래로
if (nr == n + 1) {
nr = 1;
}
if (nc == 0) {
nc = m;
}
if (nc == m + 1) {
nc = 1;
}코드트리 빵
단계별로 잘 나눠서 함수를 작성했다. 각 단계별로 디버깅을 하면서 풀이하면 디버깅 시간을 절약할 수 있다.
싸움땅
Max heap으로 해놔야 가장 큰 값이 top에 온다.
priority_queue<int, vector<int>, less<int>> pq[25][25]; //less -> max 힙, greater -> min 힙
꼬리잡기놀이
head와 tail을 잘 처리해줘야한다. 따라서 deque를 사용했다.
wind가 불 때 꼭짓점은 같은자리 2번 반복임을 빠르게 파악해야한다.
deque에서 실제 index를 찾는 방법 기억하자
for (int i = 0; i < k; ++i) {
tmp = i;
move_team();
//debug();
// 4 * n 보다 커졌을 때
if (i >= 4 * n) { tmp %= 4 * n; }
int dir = (tmp / n) % n;
sr += dx_w[dir];
sc += dy_w[dir];
//모서리는 같은 자리 2번 반복
if (prev_dir != dir) {
sr -= dx_w[dir];
sc -= dy_w[dir];
}
//cout << sr << " " << sc << "\n";
wind(sr, sc, dir);
prev_dir = dir;
//cout << ans << "\n";
}
// dq index 찾기
if (fg) {
//dq find 쓰려면 target
auto it = find(dq[team_idx].begin(), dq[team_idx].end(), target);
int real_idx = it - dq[team_idx].begin();
ans += (ll)pow(real_idx + 1, 2);
reverse(dq[team_idx].begin(), dq[team_idx].end());
}술래잡기
vector에 달팽이 경로들을 저장해서 사용하였다. 범위를 꼭 잘 지키자.
이번에는 공격이 문제에서 주어진 3 이내였다. bucketing을 사용하고
문제에 집중하자 ex) 거리 : |x1 - x2| + |y1 - y2|while (1) { for (int i = 0; i < 2; ++i) {
for (int j = 1; j <= step; ++j) {
int nr = cr + dx[cur];
int nc = cc + dy[cur];
if (j == step) {
arr.push_back({ nr, nc, (cur + 1) % 4 });
}
else {
arr.push_back({ nr,nc,cur });
}
cr = nr;
cc = nc;
if (cr == 1 && cc == 1) {
fg = 1;
break;
}
//cout << cr << " " << cc << " " << cur <<"\n";
}
if (fg == 1) { break; }
cur = (cur + 1) % 4;
}
if (fg == 1) { break; }
step++;
}
arr.pop_back();
arr.push_back({ 1,1,2 });
for (int i = arr.size() - 2; i >= arr.size() - step - 1; --i) {
arr.push_back({ arr[i].row, arr[i].col, (arr[i].dir + 2) % 4 });
}
cr = n; cc = 1;
cur = 1; step -= 1;
arr.push_back({ cr, cc, cur });
fg = 0;
while (1) {
for (int i = 0; i < 2; ++i) {
for (int j = 1; j <= step; ++j) {
int nr = cr + dx[cur];
int nc = cc + dy[cur];
if (j == step) {
int tmp = cur - 1;
if (tmp < 0) { tmp = 3; }
arr.push_back({ nr, nc, tmp });
}
else {
arr.push_back({ nr,nc,cur });
}
cr = nr;
cc = nc;
if (cr == sol_r && cc == sol_c) {
fg = 1;
break;
}
//cout << cr << " " << cc << " " << cur <<"\n";
}
if (fg == 1) { break; }
cur = (cur - 1);
if (cur < 0) { cur = 3; }
}
if (fg == 1) { break; }
step--;
}
arr.pop_back();
arr.push_back({ sol_r,sol_c, 0 });실수
is_possible, 범위 선정 집중했어야했다.
각 함수를 단계별로 디버깅해봤어야했다..
다음 공채 노려보자
