뱀
문제 해석
- 뱀이 방향을 바꾸는 시간과 다음 방향이 주어졌을 때, 몇초에 숨을 거두는지 알아내는 문제입니다.
- 0,0에서 시작하고, 오른쪽 방향으로 이동합니다.
- 주어지는 시간이 흐른 뒤에 반시계or시계방향으로 전환합니다.
- 뱀이 정해진 범위를 벗어나거나, 몸에 부딪히는 경우 숨을 거둡니다.
설계(20)
- 생각할 게 많은 구현 문제입니다.
- 먼저 좌표범위가 <= 2*10^8+1이므로 2차원 배열을 이용할 수 없습니다.
- 또한, 주어지는 시간은 최대 2*10^8이므로 1씩 카운트하는 식으로는 절대 구현이 안되는 것을 알 수 있습니다.
- 그러나 주어지는 변화수는 N<=10^3이므로 O(N^2)에 문제를 해결할 수 있습니다.
- 여기서 포인트는 벡터에 각 좌표의 선분을 저장해가면서, 벡터에 저장된 모든 좌표들과 새로운 선분을 비교하여 부딪히는지 검사를 하는 것입니다.
- 각 탐색마다 일어날 수 있는 경우는 다음과 같습니다.
- 몸통에 부딪히는 경우
- 첫번째로, 몸통과 수직으로 부딪히는 경우가 있습니다.
- 몸통(x1,y1,x2,y2), 새로운 몸통(x3,y3,x4,y4)이라고 할 때, (y1<=y3 <= y2 && x3 <= x1 <= x4)이거나 (x1<= x3 <= x2 && y3 <= y1 <=y4)일 경우 부딪힙니다. 즉, 수직으로는 한 좌표만 체크하면 됩니다. 부딪히기 까지의 길이는 새로운 몸통의 시작 Y좌표와 겹치는 좌표까지의 거리의 절대값으로 구할 수 있습니다.
- 두번째로, 몸통과 수평으로 부딪히는 경우가 있습니다.
- 두 몸통의 x좌표가 같고, y3,y4 둘중에 하나라도 y1~y2범위에 걸리면 부딪히게 됩니다.
- 만약 y좌표가 같을 경우, x3,x4와 x1~x2범위를 비교하여 체크합니다.
- 주어지는 N 중에 범위를 벗어나는 경우
- 새로운 몸통의 끝이 범위를 벗어나는 지 체크 후, 최대 값인 (L or -L)과 비교하여 길이를 구해줍니다.
- N번을 모두 검사해도 부딪히지 않은 경우
- 이는 정해진 방향으로 무언가와 부딪힐 때까지 계속 진행하게 됩니다.
- 다음 몸통의 끝을 L좌표로 정해놓은 후, 이전에 몸통과 부딪히는지 체크합니다.
- 몸통에 부딪히는 경우
구현(100)
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define INF 1e8
struct node{
int x1,y1,x2,y2;
};
vector<node> vt;
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};
int L,N,dir;
int x,y;
ll ans;
bool flag;
bool is_finished;
bool is_range(int x, int y){
return !(x< -L || x > L || y < -L || y > L);
}
ll check(int x3, int y3, int x4, int y4, vector<node> vt){
// 시작점 저장
int X = x3;
int Y = y3;
int X1 = x4;
int Y1 = y4;
if (x3 > x4) swap(x3,x4);
if (y3 > y4) swap(y3,y4);
int ans = L*2+1;
if (!is_range(X1,Y1)){
flag = true;
if (X1 < -L){
ans = min(ans,abs(X+L)+1);
}
else if (X1 > L) ans = min(ans,abs(X-L)+1);
else if (Y1 < -L) ans = min(ans,abs(Y+L)+1);
else ans = min(ans,abs(Y-L)+1);
}
for (int i = 0; i < vt.size(); i++){
int x1 = vt[i].x1;
int y1 = vt[i].y1;
int x2 = vt[i].x2;
int y2 = vt[i].y2;
if (x1 > x2) swap(x1,x2);
if (y1 > y2) swap(y1,y2);
if (x1 == x2){
if (x3 == x4){
if (x1 == x3 && ((y1 <= y3 && y3 <= y2) || (y1 <= y4 && y4 <= y2))){
ans = min(ans,min(abs(Y-y1),abs(Y-y2)));
flag = true;
}
}
else{
if (y1 <= y3 && y3 <= y2 && x3 <= x1 && x1 <= x4){
ans = min(ans,abs(Y-y3)+abs(X-x1));
flag = true;
}
}
}
else{
if (y3 == y4){
if (y1 == y3 && ((x1 <= x3 && x3 <= x2) || (x1 <= x4 && x4 <= x2))){
ans = min(ans,min(abs(X-x1),abs(X-x2)));
flag = true;
}
}
else{
if (x1 <= x3 && x3 <= x2 && y3 <= y1 && y1 <= y4){
ans = min(ans,abs(X-x3)+abs(Y-y1));
flag = true;
}
}
}
}
// 이전 경로와 부딪히지 않은 경우 길이 갱신
if (ans == L*2+1) {
return abs(x3-x4)+abs(y3-y4)+1;
}
return ans;
}
int main(){
scanf("%d %d",&L,&N);
for (int i= 0;i<N; i++){
int t;
char tmp;
scanf("%d %c",&t,&tmp);
if (flag) continue;
int nx = x + t*dx[dir];
int ny = y + t*dy[dir];
if (i) {
ans += check(x+dx[dir],y+dy[dir],nx,ny,vt);
vt.push_back({x,y,nx,ny});
}
else {
ans += check(x,y,nx,ny,vt);
vt.push_back({x,y,nx,ny});
}
x = nx;
y = ny;
if (tmp == 'L') dir = (3+dir)%4;
else dir = (dir + 1)%4;
}
// 모든 경로를 돌았는데도 종료되지 않은 경우, 쭉 같은방향으로 범위 벗어날 때까지 이동한다.
if (!flag){
int nx = x;
int ny = y;
if (N != 0){
x += dx[dir];
y += dy[dir];
}
if (dir == 0) ny = L;
else if (dir == 1) nx = -L;
else if (dir == 2) ny = -L;
else nx = L;
ans += check(x,y,nx,ny,vt);
}
printf("%lld\n",ans);
return 0;
}
디버깅
- 생각치 못한 경우가 무수히 많아 디버깅에 거의 모든 시간을 할애하였습니다.
- N이 0인 경우를 따로 처리해주어야 했습니다.
- 처음 몸통이 범위를 벗어나는 경우 또한 고려해야 했는데 하지 못했습니다.
- check함수에서 범위를 벗어나면 바로 return하도록 하는 실수를 하였습니다. 범위를 벗어나기 전에 몸통과 부딪힐 수 있는 것을 고려하여, 최소값을 갱신하도록 구현하였습니다.
제출결과
- 0ms
마무리
- 너무나 빡센 구현문제였습니다. 좌표 범위체크나 예외 케이스가 너무 많아 일반화를 시키기 너무 어려웠습니다. 이런 문제가 코딩테스트 문제로 나오면 시간안에 절대 못 풀것 같습니다.