반응형
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
문제 로직
- 골렘이 남쪽으로 갈 수 있을 때까지 내려간다.
- 골렘이 왼쪽 그리고 왼쪽 아래쪽으로 갈수있다면 왼쪽으로 구른다.
- 왼쪽으로 가지 못한다면, 골렘이 오른쪽 그리고 오른쪽 아래쪽으로 갈 수 있다면 오른쪽으로 구른다.
- 아래, 왼쪽 & 왼쪽아래, 오른쪽 & 오른쪽아래 세곳 모두 움직이지 못한다면 골렘의 숲을 탐색한다.
계속되는 실수
구른 뒤 중력을 생각했어야지
문제를 잘못 이해해서 왼쪽으로 구른다는 것을 골렘의 현재 위치 (y,x) -> 구른 뒤 위치 (y+1,x-1) 로 이해했다.
여기서 중요한 점은 (y,x) -> (y+1, x-1) 이 아닌 (y+n, x-1) ( n : 아래쪽으로 내려갈 수 있는 최대 값) 이라는 것이다.
계속 왼쪽한칸 아래한칸 만 움직이니 답이 제대로 나올리가 없었다.
애매한 위치 저장 방법
기존 코드는 탈출구 저장을 이상하게 했다. 탐색하고자 하는 위치를 기준으로 4방향 중 음수인 값이 탈출구이므로 그때 방향을 알게되는 것.
이렇게 되면 방향을 잘못 설정할 수 가 있다는 것이다. 따라서, 나는 Golem 이라는 구조체하나를 생성해서 방향 관리를 하게 되었다.
정답 코드
int main() {
// 여기에 코드를 작성해주세요.
cin >> R >> C >> K;
int ans = 0;
for (int i = 0; i < K; i++) {
int sRow, dir;
cin >> sRow >> dir;
//인덱스 0 으로 맞추기위한 빼기
//0 북 1 동 2 남 3 서
sRow -= 1;
int curY = 1;
int curX = sRow;
Golem golem;
golem.num = i + 1;
golem.y = curY;
golem.x = curX;
golem.dir = dir;
while (canMoveDown(golem)) {}
while(canMoveRL(golem)){}
if (isFull()) {
fill(&map[0][0], &map[0][0] + 80 * 80, 0);
}
else {
ans += bfs(golem);
}
}
cout << ans;
return 0;
}- 골렘의 생성위치와 골렘의 번호 및 방향을 붙여 관리
- 해당 골렘이 canMoveDown을 통해 밑으로 갈 수 있을 만큼 가고
- canMoveRL 을 통해 왼쪽으로 오른쪽으로 구를 수 있을만큼 구른 후
- 위치한 골렘이 맵을 벗어나면 초기화하거나
- 그렇지않다면 골렘의 숲을 탐색한다.
개선점
canMoveDown 과 canMoveRL을 지금보면 합칠 수 있을 것 같다. 하지만, 귀찮아서 나중에할래 ㅎㅎ
전체 코드
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include<queue>
using namespace std;
int R, C, K;
int map[80][80];
struct Golem {
int y, x;
int num;
int dir;
};
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
bool oob(int y, int x) {
return y < 0 || x < 0 || y >= R + 3 || x >= C;
}
void print() {
for (int i = 0; i < R + 3; i++) {
for (int j = 0; j < C; j++) {
cout << map[i][j] << " ";
}
cout << "\n";
}
}
void clearMap(int y, int x) {
map[y][x] = 0;
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
map[ny][nx] = 0;
}
}
bool canMove(Golem &golem, int ey, int ex) {
//초기위치 초기화
clearMap(golem.y, golem.x);
//다음 움직일 곳으로 갈수 있는지?
for (int d = 0; d < 4; d++) {
int ny = ey + dy[d];
int nx = ex + dx[d];
if (map[ny][nx] != 0 || oob(ny, nx)) {
int sy = golem.y; int sx = golem.x;
map[sy][sx] = golem.num;
for (int dd = 0; dd < 4; dd++) {
int nny = sy + dy[dd];
int nnx = sx + dx[dd];
map[nny][nnx] = golem.num;
}
map[sy + dy[golem.dir]][sx + dx[golem.dir]] = golem.num * -1;
return false;
}
}
// 움직일 수 있따면
int sy = golem.y; int sx = golem.x;
map[sy][sx] = golem.num;
for (int dd = 0; dd < 4; dd++) {
int nny = sy + dy[dd];
int nnx = sx + dx[dd];
map[nny][nnx] = golem.num;
}
map[sy + dy[golem.dir]][sx + dx[golem.dir]] = golem.num * -1;
return true;
}
void setMap(Golem & golem,int lr) {
//cout << "setMap " << ey << ex << num<<"\n";
clearMap(golem.y, golem.x);
if (lr == 1) {//right
golem.dir = (golem.dir + 1) % 4;
golem.x += 1;
golem.y += 1;
}
else if (lr == 2) { golem.dir = (golem.dir + 3) % 4;
golem.x -= 1;
golem.y += 1;
}
else if(lr == 0) {
golem.y += 1;
}
else if (lr == -1) {
}
int ey = golem.y;
int ex = golem.x;
//움직이고자 하는 위치에 맵 저장
map[ey][ex] = golem.num;
for (int dir = 0; dir < 4; dir++) {
int ny = ey + dy[dir];
int nx = ex + dx[dir];
map[ny][nx] = golem.num;
}
map[ey + dy[golem.dir]][ex + dx[golem.dir]] = golem.num * -1;
}
bool canMoveDown(Golem &golem) {
int dy = golem.y + 1;
int dx = golem.x;
if (canMove(golem, dy, dx)) {
setMap(golem, 0);
return true;
}
return false;
}
bool canMoveRL(Golem &golem) {
//현재 위치에서 오른쪽 왼쪽 갈수있는지
int y = golem.y;
int x = golem.x;
int ly = y;
int lx = x - 1;
while (canMoveDown(golem)) {}
if (canMove(golem, ly, lx) && canMove(golem, ly + 1, lx)) {
setMap(golem, 2);
while (canMoveDown(golem)) {}
//cout << "move left\n";
return true;
}
setMap(golem,-1);
//move right
int ry = y;
int rx = x + 1;
if (canMove(golem, ry, rx) && canMove(golem, ry + 1, rx)) {
setMap(golem, 1);
while (canMoveDown(golem)) {}
//cout << "move right\n";
return true;
}
setMap(golem,-1);
return false;
}
bool isFull() {
for (int i = 0; i < C; i++) {
if (map[2][i] != 0) {
return true;
}
}
return false;
}
int bfs(Golem &golem) {
queue<pair<int, int>> q;
int maxDepth = 0;
q.push({ golem.y, golem.x });
bool v[80][80];
fill(&v[0][0], &v[0][0] + 80 * 80, false);
v[golem.y][golem.x] = true;
//print();
while (!q.empty()) {
int yy = q.front().first;
int xx = q.front().second;
q.pop();
for (int d = 0; d < 4; d++) {
int ny = yy + dy[d];
int nx = xx + dx[d];
if (oob(ny, nx) || v[ny][nx])continue;
if (map[ny][nx] == 0)continue;
if (map[yy][xx] > 0) {
if (map[ny][nx] > 0) {
if (map[ny][nx] != map[yy][xx])continue;
}
else if (map[ny][nx] < 0) {
if (map[ny][nx] != -1 * map[yy][xx])continue;
}
//cout << yy << " " << xx << " " << map[ny][nx] << "-\n";
q.push({ ny,nx });
v[ny][nx] = true;
maxDepth = max(maxDepth, ny);
}
else if (map[yy][xx] < 0) {
//cout << yy << " " << xx << " " << map[yy][xx] << " " << map[ny][nx] << "-\n";
q.push({ ny,nx });
v[ny][nx] = true;
maxDepth = max(maxDepth, ny);
}
}
}
//cout << "값 : " << maxDepth - 2 <<"\n";
return maxDepth - 2;
}
int main() {
// 여기에 코드를 작성해주세요.
cin >> R >> C >> K;
int ans = 0;
for (int i = 0; i < K; i++) {
int sRow, dir;
cin >> sRow >> dir;
//인덱스 0 으로 맞추기위한 빼기
//0 북 1 동 2 남 3 서
sRow -= 1;
int curY = 1;
int curX = sRow;
Golem golem;
golem.num = i + 1;
golem.y = curY;
golem.x = curX;
golem.dir = dir;
while (canMoveDown(golem)) {}
while(canMoveRL(golem)){}
if (isFull()) {
fill(&map[0][0], &map[0][0] + 80 * 80, 0);
}
else {
ans += bfs(golem);
}
}
cout << ans;
return 0;
}반응형
'BOJ' 카테고리의 다른 글
| [BOJ 1011] Fly me to the Alpha Centauri (0) | 2024.08.11 |
|---|---|
| [BOJ 2011] 암호코드 (0) | 2024.04.21 |
| [BOJ 2531] 회전 초밥 (0) | 2024.03.08 |
| [BOJ 2146] 다리 만들기 (0) | 2024.01.26 |
| [백준 1018번] 체스판 다시 칠하기 (0) | 2021.05.03 |