[백준 10875] 뱀 (C++)

문제 링크: https://www.acmicpc.net/problem/10875

10875번: 뱀

1. 주의할 점

- 연산이 헷갈리지 않도록 변수를 사용하여 연산값을 저장한다

- 10^8*2 * 10^8*2 만큼의 배열을 생성하지 않고 직전 형태의 뱀의 일부를 Vector에 시작점, 방향, 길이 만큼 저장한다

 

2. 구현

-  V 벡터에 뱀 몸 일부의 X,Y,길이,방향을 저장한다

- Temp의 값을 최대로 지정하고, 해당 위치에서(뱀의 머리) 입력받은 시간 Val을 더했을 때, 벽에 부딪힌다면 Temp값을 갱신한다(|벽 - 시작점| +1). 각 방향마다 벽과 시작점 사이의 거리가 다르므로 4방향 모두 직접 지정한다

- V 벡터의 길이가 1이상일 때, 반복문을 실행하지만, 가장 최근에 추가된 부분과 현재 이동하려는 방향은 부딪힐 일이 없으므로 V.size()-1까지만 반복문을 수행한다 (원래는 2개 더 빼도 되는데 처리하기 귀찮았다)

- 뱀의 머리와 기존 뱀의 일부와 부딪히는 경우는 밑의 사진과 같이 16가지 경우에 대해 고려하여 작성하였다 (사진에서는 12가지만 보인다)

 

(사진의 검정부분이 앞으로 머리가 진행할 부분, 빨간 부분이 이미 존재하는 뱀의 일부)

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
struct info {
	long long sx, sy, dir, len;
};
info tmp;
vector<info> v;
long long limit, order, val;
char c;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> limit >> order;
	bool finish = false;
	long long result = 0;
	long long cx = 0, cy = 0, cd = 1, val, nx, ny;		//현재 위치, 방향
	for (int i = 0; i <= order; i++) {
		if (i != order)
			cin >> val >> c;
		else if (i == order)
			val = 987654321;
		if (finish) continue;		//이미 끝난 경우
		long long temp = 987654321;
		//바깥쪽으로 나가지는 경우
		nx = cx + dx[cd] * val;
		ny = cy + dy[cd] * val;
		if (nx < -limit) 		temp = min(temp, cx - (-limit) + 1);
		else if (nx > limit) 	temp = min(temp, limit - cx + 1);
		else if (ny < -limit) 	temp = min(temp, cy - (-limit) + 1);
		else if (ny > limit) 	temp = min(temp, limit - cy + 1);

		if (v.size() > 0) {		//마지막 길이와는 비교할 필요 없음
			for (int j = 0; j < v.size() - 1; j++) {
				long long sx = v[j].sx;
				long long sy = v[j].sy;
				long long len = v[j].len;
				long long dir = v[j].dir;
				long long ex = sx + dx[dir] * len;
				long long ey = sy + dy[dir] * len;
				//몸통과 부딪히는 경우
				if (cd == 0) {
					if (dir == 0 && cx == sx && cy <= sy && sy <= ny) 
						temp = min(temp, sy - cy);
					else if (dir == 1 && sx <= cx && cx <= ex && cy <= sy && sy <= ny) 
						temp = min(temp, sy - cy);
					else if (dir == 2 && cx == sx && cy <= ey && ey <= ny) 
						temp = min(temp, ey - cy);
					else if (dir == 3 && ex <= cx && cx <= sx && cy <= ey && ey <= ny) 
						temp = min(temp, ey - cy);
				}
				else if (cd == 1) {
					if (dir == 0 && cx <= sx && sx <= nx && sy <= cy && cy <= ey) 
						temp = min(temp, ex - cx);
					else if (dir == 1 && cy == sy && cx <= sx && sx <= nx) 
						temp = min(temp, sx - cx);		
					else if (dir == 2 && cx <= sx && sx <= nx && ey <= ny && ny <= sy)
						temp = min(temp, sx - cx);

					else if (dir == 3 && cy == sy && cx <= ex && ex <= nx)
						temp = min(temp, ex - cx);
				}
				else if (cd == 2) {
					if (dir == 0 && cx == sx && ny <= ey && ey <= cy)
						temp = min(temp, cy - ey);
					else if (dir == 1 && sx <= cx && cx <= ex && ny <= sy && sy <= cy)
						temp = min(temp, cy - ey);
					else if (dir == 2 && cx == sx && ny <= sy && sy <= cy)
						temp = min(temp, cy - sy);
					else if (dir == 3 && ny <= sy && sy <= cy && ex <= cx && cx <= sx)
						temp = min(temp, cy - sy);
				}
				else if (cd == 3) {
					if (dir == 0 && sy <= cy && cy <= ey && nx <= ex && ex <= cx)
						temp = min(temp, cx - sx);
					else if (dir == 1 && sy == cy && nx <= ex && ex <= cx)
						temp = min(temp, cx - ex);
					else if (dir == 2 && nx <= sx && sx <= cx && ey <= cy && cy <= sy)
						temp = min(temp, cx - ex);
					else if (dir == 3 && sy == cy && nx <= sx && sx <= cx)
						temp = min(temp, cx - sx);
				}
			}
		}
		if (temp != 987654321) {
			finish = true;
			result += temp;
		}
		else {
			tmp.dir = cd;
			tmp.sx = cx;
			tmp.sy = cy;
			tmp.len = val;
			v.push_back(tmp);
			cx = nx;
			cy = ny;
			//방향 전환
			if (c == 'L') cd = (cd + 3) % 4;
			else cd = (cd + 1) % 4;
			result += val;			
		}
	}
	cout << result;
	system("pause");
	return 0;
}