[백준 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벡터에 저장했다.
함수에대한 설명은 굉장히 직관적이므로 코드에 주석을 달아놓았고,
핵심인 중요한점 몇가지가 있다.

1. N 이 0이면 오른쪽격자칸밖(오른쪽벽으로 생각하자.)으로 나가서 죽게된다.
2. N개의 뱀머리 회전에도 뱀이 살아남았다해도, 문제에 적힌대로는 마지막 방향대로 쭉 몸을 늘린다.(이동한다.)
3. 시간은 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;
}