3190 뱀

https://www.acmicpc.net/problem/3190

3190번: 뱀

 

간단하고 재밌던 문제이다. 특정 시간에 어디로 회전하라는 입력을 어떻게 처리할지 고민했는데 char 배열을 만들어서 해결했다. 나쁘지 않은 방법인 것 같다. 

처음엔 꼬리가 길때 머리를 따라오는 것을 어떻게 구현해야 할지 막막했는데 큐나 덱을 사용하면 해결할 수 있었다. 뱀이 이동할 때마다 덱의 Back(꼬리)을 pop하고, Front(머리)에 다음 좌표를 집어넣으면 뱀의 이동을 구현할 수 있다. 

그 후 머리가 몸에 부딪혔을 경우를 감지하기 위해 board에서 뱀이 있는 부분은 1로 했다.

#include <bits/stdc++.h>
using namespace std;

int N,K,L,x,y,dir=0,cnt=0;
int board[103][103];
char movedata[10003];
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
//dir 0이 오른쪽임. (90도 오른쪽방향으로 회전) 

deque<pair<int,int>> deq;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>K;
	for(int i=0;i<K;i++){
		int r,c; cin>>r>>c;
		board[r-1][c-1]=2;
	}
	cin>>L;
	for(int i=0;i<L;i++){
		int x; char c;
		cin>>x>>c;
		movedata[x]=c;
	}
	
	//초기 위치 설정 
	deq.push_front({0,0});
	board[0][0]=1;
	
	while(true){
		cnt++;
		int ny=y+dy[dir];
		int nx=x+dx[dir];
		//벽에 부딪혔거나 OOB면 finish; 
		if(ny<0||nx<0||ny>=N||nx>=N||board[ny][nx]==1){ 
			cout<<cnt;
			return 0;
		}
		else{
			//이동한 칸에 사과(2)가 있다면
			if(board[ny][nx]==2){
				deq.push_front({ny,nx});
				board[ny][nx]=1;
			}
			//아니라면
			else{
				board[deq.back().first][deq.back().second]=0;
				deq.pop_back();
				deq.push_front({ny,nx});
				board[ny][nx]=1;
			}
			y=ny; x=nx; 
		}
		//회전하기
		if(movedata[cnt]=='L') dir--;
		if(movedata[cnt]=='D') dir++;
		if(dir<0) dir=3;
		if(dir>3) dir=0;
	}
	cout<<cnt;
	return 0;
}