백준 3190 [C++]

www.acmicpc.net/problem/3190

3190번: 뱀

1. 풀이방법

 

- 문제의 그대로를 구현하면 되는 문제인데.. 아마 20대 중후반 분들은 한번쯤은 해보시지 않았을까....

 

- 저의 방법은 머리와 꼬리의 현재좌표를 계속 갱신하는 것인데...

 

- 핵심은 머리가 지나가면서 자신이 어디로 지나갔었는지를 지도에 기록을 해놓아야 하는 것.

 

- 사과가 없어서 꼬리가 짧아 져야 할 경우 지도에 기록해둔 머리가 갔던 방향(꼬리 좌표에서)을 확인하고 그 방향으로       이동합니다.. (directionjirung[][])

 

- 방향전환 명령어는 큐를 이용해서 pair의 first(시간) 이 게임시간과 일치할 때 pop을 하여 썼습니다.

 

 

 

2. 주의할 점

 

- 하.....전 꽤 오래 걸렸는데....아이디어를 생각하고 구현한게 어려운게 아니라...

 

- 변수를 수정할때 조심해야할 것...

tailx+=directionjirung[tailx][taily]; //이 따구로 하면 변경된 tailx가

taily+=directionjirung[tailx][taily]; //여기에 반영되기 때문에 매우 엉망인 값이 나옵니다..

 

- <변경된 코드는 이렇습니다>

int tmpx=tailx;

int tmpy=taily;

tailx+=directionjirung[tmpx][tmpy];

taily+=directionjirung[tmpx][tmpy];

 

기본적인 실수를 하고도 못찾아서 한참을 찾았네요.....지도도 출력하고...;;

 

이제부터 더 주의해서 세심하게 코드를 짜야겠습니다

 

감을 다시 잡아야겠네요....

 

 

3. 나의코드

 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int map[101][101]; //사과가 있는지 여부를 알기 위해
int jirung[101][101];//지렁이의 현재위치
int directionjirung[101][101]; //꼬리를 위한 지렁이가 그 좌표에서 보고있던 방향을 기록
int N;
int K;
int dx[4] = {0,1,0,-1}; //동남서북
int dy[4] = {1,0,-1,0};
int direction=0; //지렁이가 보고있는 방향(처음엔 동쪽 보고있다.)
int gamesecond;
int L;
int headx, heady,tailx,taily;
queue<pair<int, char>> dq;

void setapple() {
	int x, y;
	for (int i = 0; i < K; i++) {
		cin >> x >> y;
		map[x][y] = 1; //사과가 존재하는 위치
	}
}
void setqueue() {
	pair<int, char> tmppair;
	for (int i = 0; i < L; i++) {
		cin >> tmppair.first >> tmppair.second;
		dq.push(tmppair);
	}
}

int main() {
	cin >> N >> K;
	setapple();
	cin >> L;
	setqueue();
	headx = 1; heady = 1; tailx = 1; taily = 1;
	jirung[1][1] = 1;
	while (1) {
		while (1) {
			if (dq.empty() == false && gamesecond == dq.front().first) {
				if (dq.front().second == 'L') { //왼쪽 회전
					direction = (direction + 3) % 4;
				}
				else {//오른쪽 회전
					direction = (direction + 1) % 4;
				}
				dq.pop();
			}
			else break;
		}
		gamesecond++;

		directionjirung[headx][heady] = direction; //꼬리를위해 방향을 기록먼저 !
		headx += dx[direction]; heady += dy[direction];
		if (headx <= 0 || heady <= 0 || headx > N || heady > N || jirung[headx][heady] == 1) {  break; } //종료조건 (map의 범위 1~N)

		jirung[headx][heady] = 1; //머리가 도착한 곳 표시
		if (map[headx][heady] == 1) { //사과가 있다면
			map[headx][heady] = 0; 
		}
		else {
			jirung[tailx][taily] = 0; //사과가 없다면 꼬리좌표 지워짐
			int tmptailx = tailx;
			int tmptaily = taily;
			tailx = tailx + dx[directionjirung[tmptailx][tmptaily]]; //꼬리의 위치 업데이트 (머리가 지나갈때 간 방향으로 업데이트)
			taily = taily + dy[directionjirung[tmptailx][tmptaily]];
		}
	}
	cout << gamesecond << "\n";
			return 0;
}