[백준 C++] 10875 뱀
문제
가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 (−L, −L), 그리고 맨 오른쪽 맨 위 칸의 좌표는 (L, L)이다. x좌표는 왼쪽에서 오른쪽으로 갈수록, y좌표는 아래에서 위로 갈수록 증가한다.
이 격자판의 (0, 0) 칸에 한 마리의 뱀이 자리를 잡고 있다. 처음에는 뱀의 크기가 격자판의 한 칸의 크기와 같으며, 뱀의 머리는 격자판의 오른쪽을 바라보고 있다. 이 뱀은 자신이 바라보고 있는 방향으로 1초에 한 칸씩 몸을 늘려나가며, 뱀의 머리는 그 방향의 칸으로 옮겨가게 된다. 예를 들어 위의 그림과 같이 L = 3인 경우를 생각해 보자. 뱀은 처음에 (0, 0)에 있으며, 그 크기는 격자판 한 칸 만큼이고, 뱀의 머리가 바라보고 있는 방향은 오른쪽이다. 1초가 지나고 나면 이 뱀은 몸을 한 칸 늘려서 (0, 0)과 (1, 0)의 두 칸을 차지하게 되며, 이때 (1, 0) 칸에 뱀의 머리가 놓이게 된다. 1초가 더 지나고 나면 (0, 0), (1, 0), (2, 0)의 세 칸을 차지하게 되고, 뱀의 머리는 (2, 0)에 놓이게 된다.
이 뱀은 자신의 머리가 향하고 있는 방향을 일정한 규칙에 따라 시계방향, 혹은 반시계방향으로 90도 회전한다. 1번째 회전은 뱀이 출발한지 t1 초 후에 일어나며 i(i > 1)번째 회전은 i − 1번째 회전이 끝난 뒤 ti 초 후에 일어난다. 단, 뱀은 ti 칸 만큼 몸을 늘린 후에 머리를 회전하며 머리를 회전하는 데에는 시간이 소요되지 않는다고 가정한다.
만일 뱀의 머리가 격자판 밖으로 나가게 되면, 혹은 뱀의 머리가 자신의 몸에 부딪히게 되면 이 뱀은 그 즉시 숨을 거두며 뱀은 숨을 거두기 직전까지 몸을 계속 늘려나간다.
뱀이 머리를 회전하는 규칙, 즉 ti 와 그 방향에 대한 정보가 주어졌을 때, 뱀이 출발한지 몇 초 뒤에 숨을 거두는지를 알아내는 프로그램을 작성하라.
입력
첫 번째 줄에 정수 L(1 ≤ L ≤ 108)이 주어진다. 두 번째 줄에는 머리의 방향을 몇 번 회전할 것인지를 나타내는 정수 N(0 ≤ N ≤ 103)이 주어진다. 다음 N 개의 줄에 뱀이 머리를 어떻게 회전하는지에 대한 정보가 주어진다. i(1 ≤ i ≤ N)번째 줄에 정수 ti(1 ≤ ti ≤ 2 · 108)와 diri 가 차례로 주어지며 diri 는 문자 L, 또는 R 중 하나이다. 뱀은 i = 1인 경우 출발, 그 외의 경우엔 i − 1번째 회전으로부터 ti 초 후에 diri 의 방향으로 머리를 회전하며, 만일 diri 가 L 이라면 왼쪽 (반시계방향)으로, R 이라면 오른쪽 (시계방향)으로 90도 회전한다.
출력
첫 번째 줄에 답을 나타내는 값을 하나 출력한다. 이 값은 뱀이 출발한지 몇 초 후에 숨을 거두는지를 나타낸다.
https://www.acmicpc.net/problem/10875
풀이
일반적인 방법으로 한칸한칸 움직이면 시간초과 + 메모리초과 세트이다.
뱀이 한턴에 최대 이동가능한 거리(시간)가 2억이고, 최대 1000번 뱀이 머리방향을 회전하므로 1001 x 200000000 번...
따라서, 매턴마다 움직인 궤적을 시작좌표x,y와방향dir,움직인거리distance 총 4가지요소를 std::pair로 묶어서 order벡터에 저장했다.
함수에대한 설명은 굉장히 직관적이므로 코드에 주석을 달아놓았고,
핵심인 중요한점 몇가지가 있다.
- N 이 0이면 오른쪽격자칸밖(오른쪽벽으로 생각하자.)으로 나가서 죽게된다.
- N개의 뱀머리 회전에도 뱀이 살아남았다해도, 문제에 적힌대로는 마지막 방향대로 쭉 몸을 늘린다.(이동한다.)
- 시간은 long long 형으로 계산해야한다. 여기서 시간은 곧 거리이므로, 1001 x 200000000 => 0이11자리이므로..
문제가 모든예외 상황들을 빠짐없이 체크하도록 강요한다.
테스트 케이스가 별로없어서 풀기어렵게 느껴진다.
자세한건 아래 코드를 참고
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//매번 order리스트를 탐색하며, 이동에 걸림돌이되는가 확인
//가능하면 현재 정보를 order에 추가, 현재위치 x, y, 방향dir을 갱신
using std::vector; using std::pair;
typedef pair<long, long> pll;
long x, y, dir = 1; //뱀 위치, 방향(1:우 2:하 3:좌 4:상//
//시작위치<x1, y1> 에서 방향과 거리<dir, distance>만큼 이동을 기록
vector<pair<pll, pll>> order, die;
long L, N;
long long t=0;
long left=-1, right, up=-1, down; //4방향 벽
long dx[5] = {0, 0, 1, 0, -1};
long dy[5] = {0, 1, 0, -1, 0};
bool isRight(long x, long y, long dir, long distance);
void nextDir();
void move(long distance);
void saveOrder(long x, long y, long dir, long distance);
void calculate(long distance);
//프로그램의 메인부분
void snakeMOVE() {
if (N == 0) { //N이 0 이더라도 한번 입력받아야하고, 오른쪽 벽 끝까지 뱀이 나아간다.
long distance;
scanf("%ld", &distance);
printf("%d", right - x);
return;
}
while (N--) {
long distance; //이동할거리
scanf("%ld", &distance);
if (!isRight(x, y, dir, distance)) { //이동이 불가능하면
calculate(distance); //출력후
return; //프로그램 종료
}
saveOrder(x, y, dir, distance);
move(distance);
nextDir();
}
//모든 입력을 받은후 에도 부딪히지 않고 생존했다면
long distance; //현재 바라보는 방향으로 이동할 수 있는 거리(벽이나 몸통까지의 거리)
if (dir == 1)
distance = right - y - 1; //벽에 부딪히기 전까지감
else if (dir == 2)
distance = down - x - 1;
else if (dir == 3)
distance = y - left - 1;
else if (dir == 4)
distance = x - up - 1;
if (!isRight(x, y, dir, distance)) {
calculate(distance);
}
else {
t += distance + 1; //현재방향대로 이동후 숨을 거두게됨
printf("%lld", t);
}
return;
}
//뱀이 현재방향으로 이동시 몇초뒤에 사망하는지 출력하는 함수
//이미 isRight함수에서 die 벡터에 추가시에,
//x좌표, y좌표 둘다 비교했으므로
//이 함수에서는 x좌표, y좌표중 하나만 비교해도 됨.
void calculate(long distance) {
long long min = 0x7fffffffffffffff; //long long 최댓값
if (die.size() == 0) { //맵밖으로 벗어난경우
//min값을 맵밖으로 벗어나는데 까지 걸리는 시간으로 계산
if (dir == 1)
min = right - y;
else if (dir == 2)
min = down - x;
else if (dir == 3)
min = y - left;
else if (dir == 4)
min = x - up;
}
//뱀이 이동하다가 기존 궤적에 부딪히는 최소 거리(시간)을 계산
for (int i = 0; i < die.size(); i++) {
long ox = die[i].first.first;
long oy = die[i].first.second;
long odir = die[i].second.first;
long odis = die[i].second.second;
long temp = 0;
if (dir == 1) {
if (odir == 1 || odir == 2 || odir == 4) temp = oy - y;
if (odir == 3) temp = ( oy + dy[odir]*odis ) - y;
}
else if (dir == 2) {
if (odir == 2 || odir == 1 || odir == 3) temp = ox - x;
if (odir == 4) temp = (ox + dx[odir] * odis) - x;
}
else if (dir == 3) {
if (odir == 3 || odir == 2 || odir == 4) temp = y - oy;
if (odir == 1) temp = y - (oy + dy[odir] * odis);
}
else if (dir == 4) {
if (odir == 4 || odir == 1 || odir == 3) temp = x - ox;
if (odir == 2) temp = x - (ox + dx[odir] * odis);
}
if (min > temp) {
min = temp; //최소시간 계산
}
}
//출력하는부분
printf("%lld", min + t);
}
//뱀의 이동궤적을 order에 저장하는 함수
void saveOrder(long x, long y, long dir, long distance) {
pll p1 = { x, y }, p2 = { dir, distance };
order.push_back({ p1, p2 });
}
//입력받은 거리(시간)만큼 뱀을 이동시키는 함수
void move(long distance) {
x += dx[dir] * distance; //현재 위치 이동
y += dy[dir] * distance;
//이동후 시간 t 증가
t += distance;
}
//뱀머리 방향을 입력받아 설정하는 함수
void nextDir() {
char d;
scanf("%c%c", &d, &d);
if (d == 'L')
dir--;
else if (d == 'R')
dir++;
if (dir == 0)
dir = 4;
if (dir == 5)
dir = 1;
scanf("%c", &d); //줄바꿈문자 지움
}
//뱀머리가 이동가능 한지 확인하는 함수
//불가능하다면 die 벡터에 불가능한 뱀의 이동 궤적(order[i])을 추가
bool isRight(long x, long y, long dir, long distance) {
bool res = true;
long xx = x + dx[dir] * distance; //다음 위치
long yy = y + dy[dir] * distance;
//맵밖으로 벗어나는지 확인
if (yy <= left || right <= yy ||
xx <= up || down <= xx)
return false;
//기존 뱀의 이동궤적과 부딪히는지 확인
for (int i = 0; i < order.size(); i++) {
if (i == order.size() - 1) continue; //바로 직전의 뱀이 움직인 궤적은 제외
long ox = order[i].first.first;
long oy = order[i].first.second;
long odir = order[i].second.first;
long odis = order[i].second.second;
if (dir == 1) {
if (odir == 1 && x == ox) //x→ o→
if (y <= oy && oy <= yy) { res = false; die.push_back(order[i]); }
if (odir == 3 && x == ox) //x→ ←o
if (y <= oy + dy[odir]*odis && oy + dy[odir] * odis <= yy) { res = false; die.push_back(order[i]); }
//y좌표가 서로 교차하는가?
if (y <= oy && oy <= yy) { //x→ |o
//x좌표가 서로 교차하는가?
if (odir == 2 && ox <= x && x <= ox + dx[odir] * odis) { res = false; die.push_back(order[i]); }
if (odir == 4 && ox + dx[odir] * odis <= x && x <= ox) { res = false; die.push_back(order[i]); }
}
}
else if (dir == 2) {
if (odir == 2 && y == oy) //x↓
//o↓
if (x <= ox && ox <= xx) { res = false; die.push_back(order[i]); }
if (odir == 4 && y == oy) //x↓
//o↑
if (x <= ox + dx[odir]*odis && ox + dx[odir] * odis <= xx) { res = false; die.push_back(order[i]); }
//x좌표가 서로 교차하는가?
if (x <= ox && ox <= xx) { //x↓
//oㅡ
//y좌표가 서로 교차하는가?
if (odir == 1 && oy <= y && y <= oy + dy[odir] * odis) { res = false; die.push_back(order[i]); }
if (odir == 3 && oy + dy[odir] * odis <= y && y <= ox) { res = false; die.push_back(order[i]); }
}
}
else if (dir == 3) {
if (odir == 3 && x == ox) //o← ←x
if (yy <= oy && oy <= y) { res = false; die.push_back(order[i]); }
if (odir == 1 && x == ox) //o→ ←x
if (yy <= oy + dy[odir] * odis && oy + dy[odir]*odis <= y) { res = false; die.push_back(order[i]); }
//y좌표가 서로 교차하는가?
if (yy <= oy && oy <= y) { //o| ←x
//x좌표가 서로 교차하는가?
if (odir == 2 && ox <= x && x <= ox + dx[odir] * odis) { res = false; die.push_back(order[i]); }
if (odir == 4 && ox + dx[odir] * odis <= x && x <= ox) { res = false; die.push_back(order[i]); }
}
}
else if (dir == 4) {
if (odir == 4 && y == oy) //o↑
//x↑
if (xx <= ox && ox <= x) { res = false; die.push_back(order[i]); }
if (odir == 2 && y == oy) //o↓
//x↑
if (xx <= ox + dx[odir] * odis && ox + dx[odir]*odis <= x) { res = false; die.push_back(order[i]); }
//x좌표가 서로 교차하는가?
if (xx <= ox && ox <= x) { //oㅡ
//x↑
//y좌표가 서로 교차하는가?
if (odir == 1 && oy <= y && y <= oy + dy[odir] * odis) { res = false; die.push_back(order[i]); }
if (odir == 3 && oy + dy[odir] * odis <= y && y <= oy) { res = false; die.push_back(order[i]); }
}
}
}
return res;
}
int main(void) {
scanf("%ld%ld", &L, &N);
right = 2 * L + 1;
down = 2 * L + 1;
x = L;
y = L;
snakeMOVE();
return 0;
}
Author And Source
이 문제에 관하여([백준 C++] 10875 뱀), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cldhfleks2/10875저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)