BOJ
BOJ::10875 뱀
BOJ Gold 1
BOJ::10875 뱀
- Link : BOJ::10875
- Link : baactree
- Level : Gold 1
- tag : implementation
시사점
- 정말 좋은 구현문제입니다.
- 턴의 갯수만큼을 이용하여 선분을 넘어가는지 안 넘어가는지 체크할 생각까진 하였지만,
- 이런 류의 유형은 구체적으로 풀어본 적이 없어서, bacctree님의 블로그를 참고하였습니다.
- 꼭 기억해두어야 할 유형이라고 생각합니다.
이해(x)
- L ( 1 <= L <= 10^8), N(0 <= N <= 10^3)인 입력이 주어집니다.
- L은 전체 맵의 사이즈를 나타내는데 사용됩니다.
- N은 뱀이 방향을 회전하는 갯수입니다.
- 뱀은 맵을 벗어나거나, 자신의 몸에 머리가 닿는 경우 숨을 거둡니다.
- 출발한지 몇 초후에 숨을 거두는지 출력합니다.
설계, 손 코딩(x)
- 손으로 중심이 되는 코드를 구현합니다.
- L만 봐도 알겠지만, 범위가 매우 커서 배열에 담을 수 없습니다.
- 또한, {x, y}를 map에 넣어서 이분탐색을 이용해보려고 생각해보아도,
- 그렇다고 거리를 구하기가 쉽지 않습니다.
- 따라서, 선분을 이용하여 풀이해야 합니다.
- 즉, {x1, y1, x2, y2, dir} 로 이루어진 선분을 구성합니다.
- 가로 선분인지, 세로 선분인지를 vector에 저장해놓고,
- 현재 방향으로 뱀이 몇칸 가면 그 선분들 중 하나를 만나게 되는지 확인하면 됩니다.
- 눈여겨 보아야 할 점은, 당연하게도 선분을 체크하는 부분입니다.
- 현재 뱀의 머리가 있는 곳이 x, y 일때,
- min(그 방향으로 계속가면 숨을 거두는 이동 수, 다음 회전까지 남은 이동수)
- 를 취하여 이동하면 됩니다.
- 보시다시피, 숨을 거두는 이동 수가, 다음 회전까지 남은 시간보다 작게되면,
- 게임을 종료시킵니다.
복잡도
- T : O(N^2)
구현(x)
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1};
const int MAXN = 1000 + 1;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct Line{
int dir;
int x1, y1, x2, y2;
Line(){}
Line(int a, int b, int c, int d) : x1(a), y1(b), x2(c), y2(d){
if(b == d)
dir = 0;
else
dir = 1;
set_point();
}
void set_point(){
if(x1 > x2)
swap(x1, x2);
if(y1 > y2)
swap(y1, y2);
}
};
int L, n;
pair<int,int> turn[MAXN];
vector<Line> line;
void input(){
cin >> L >> n;
rep(i, 0, n){
char ch;
cin >> turn[i].first >> ch;
turn[i].second = (ch == 'L' ? -1 : 1);
}
turn[n++] = {inf, -1};
line.push_back(Line(-L-1, -L-1, L+1,-L-1));
line.push_back(Line(-L-1, L+1, L+1, L+1));
line.push_back(Line(-L-1, -L-1, -L-1, L+1));
line.push_back(Line( L+1, -L-1, L+1, L+1));
}
void simulate(){
ll ans = 0;
int x = 0, y = 0, d = 0;
rep(i, 0, n){
int t = inf;
rep(j, 0, line.size()){
if(line[j].dir == 0){
if(d == 0){
if(y == line[j].y1 && x < line[j].x1)
t = min(t, line[j].x1 - x);
}else if(d == 1){
if(line[j].x1 <= x && x <= line[j].x2 && y < line[j].y1)
t = min(t, line[j].y1 - y);
}else if(d == 2){
if(y == line[j].y1 && line[j].x2 < x)
t = min(t, x - line[j].x2);
}else{
if(line[j].x1 <= x && x <= line[j].x2 && y > line[j].y1)
t = min(t, y - line[j].y1);
}
}else{
if(d == 0){
if(line[j].y1 <= y && y <= line[j].y2 && x < line[j].x1)
t = min(t, line[j].x1 - x);
}else if(d == 1){
if(line[j].x1 == x && y < line[j].y1)
t = min(t, line[j].y1 - y);
}else if(d == 2){
if(line[j].y1 <= y && y <= line[j].y2 && line[j].x1 < x)
t = min(t, x - line[j].x1);
}else{
if(line[j].x1 == x && y > line[j].y2)
t = min(t, y - line[j].y2);
}
}
}
if(t <= turn[i].first){
cout << ans + t << endl;
return;
}
ans += turn[i].first;
int nx = x + dx[d] * turn[i].first, ny = y+dy[d] * turn[i].first;
line.push_back(Line(x, y, nx, ny));
if(turn[i].second == -1)
d = (d+1) % 4;
else
d = (d+3) % 4;
x = nx, y = ny;
}
}
void process(){
input();
simulate();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
process();
return 0;
}