뱀

www.acmicpc.net/problem/3190

3190번: 뱀

 

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<deque>
#include<math.h>
#include<cmath>

using namespace std;

int n, k;

int dy[] = {1,-1,0,0};
int dx[] = {0,0,1,-1};
 
int snakearr[101][101]; //벰의 몸통을 저장하는 배열
struct info {

	deque<pair<int, int>>dq; //뱀이 차지하는 위치를 dq 에 넣어준다.
	int dir; // 뱀이 다니고 있는 방향
	int time; // 시간

};

bool canGo(int x, int y, int n)
{
	return x >= 0 && y >= 0 && x < n && y < n && snakearr[x][y]==0;
}


bool movesnake( info& nowSnake, vector<vector<int>>&arr ,int dirIdx) {

	

	pair<int, int> head = nowSnake.dq.back(); //뱀의 머리는 dq 뒤쪽에
	pair<int, int>tail = nowSnake.dq.front(); //뱀의 꼬리는 dq 앞쪽에
	deque<pair<int, int>>dq = nowSnake.dq; 

	int dir = nowSnake.dir;
	int time = nowSnake.time;



	int nx = head.first + dx[dirIdx]; //새로운 위치
	int ny = head.second + dy[dirIdx];

	if (canGo(nx, ny, n)) { //벽에 부딪히는지, 자기 몸에 부딪히는지 확인
		
		time += 1;   //시간 증가
		dir = dirIdx;  // 가고자 하는 방향
		
		head = { nx,ny }; 
		snakearr[nx][ny] = 1; //새로운 위치 1로 
		
		dq.push_back(head); 
		
		if (arr[nx][ny] == 0) { //사과가 없는 경우
			snakearr[tail.first][tail.second] = 0;  //꼬리부분 0으로 만들어주기
			dq.pop_front(); //뱀의 몸통 위치 저장하는 deque pop_front()
		}
		else { //사과가 있는 경우
			arr[nx][ny] = 0; //사과 먹었으니까 0으로
		}

		nowSnake = { dq,dir,time }; //현재 뱀의 상태 갱신

	}
	else { //부딪히게 되면 time 증가시키고 false반환
		nowSnake.time += 1;
		return false;
	}

	return true;

}


int simulate(info& nowSnake, map<int, char>&move , vector<vector<int>>&arr) {


	
	while (1) {

		int dir = nowSnake.dir;
		int time = nowSnake.time;

		if (move.find(time)!=move.end()) { //해당 시간에 방향전환 하는지 확인
			
			char direction = move[time];
		
			if (direction == 'D') { //오른쪽으로 돌아야 할때

				if (dir == 0) { //오
					if (movesnake(nowSnake, arr, 2) == false) { break; } //내가 보는기준 아래
				}
				else if (dir == 1) {// 왼
					if (movesnake(nowSnake, arr, 3) == false) { break; }//내가 보는기준 위
				}
				else if (dir == 2) {// 아래
					if (movesnake(nowSnake, arr, 1) == false) { break; }//내가 보는기준 왼
				}
				else if (dir == 3) {//위
					if (movesnake(nowSnake, arr, 0) == false) { break; }//내가 보는기준 오
				}
			
			}
			else if (direction == 'L') { //왼쪽으로 돌아야할 때
				
				if (dir == 0) { //오
					if (movesnake(nowSnake, arr, 3) == false) { break; } //내가 보는기준 위
				}
				else if (dir == 1) { //왼
					if (movesnake(nowSnake, arr, 2) == false) { break; }//내가 보는기준 아래
				}
				else if (dir == 2) { //아래
					if (movesnake(nowSnake, arr, 0) == false) { break; }//내가 보는기준 오
				}
				else if (dir == 3) { 위
					if (movesnake(nowSnake, arr, 1) == false) { break; }//내가 보는기준 왼
				}

			
			}
		}
		else { //방향 전환을 안하는 경우 
			if (movesnake(nowSnake, arr, dir) == false) { break; }  
		}

	}

	return nowSnake.time;

}





int main() {

	cin >> n;
	cin >> k;

	vector<vector<int>>arr(n, vector<int>(n, 0));

	memset(snakearr, 0, sizeof(snakearr));
	for (int i = 0; i < k; i++) {
	
		int x, y;
		cin >> x;
		cin >> y;

		arr[x-1][y-1] = 1; //사과의 위치 저장
	}
	
	int l;
	
	deque<pair<int, int>>dq;
	dq.push_back(make_pair(0, 0));
	info snakeInfo = { dq ,0,0 };

	cin >> l;

	map<int, char>move;
	
	for (int i = 0; i < l; i++) {
		
		int time;
		char dir;
		cin >> time;
		cin >> dir;
		move[time] = dir;
	
	}

	snakearr[0][0]=1;

	cout<<simulate(snakeInfo,move,arr);
	

}

<JAVA>

package Samsung;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class 뱀 {

	
	static int n,k;
	static int[][] arr;
	static StringTokenizer st;
	static HashMap<Integer,Character>hm= new HashMap<>();
	static int[]dx = {1,0,-1,0};
	static int[]dy = {0,-1,0,1}; //아래 왼 위 오
	
	
	static class Pair{
		int t;
		char dir;
		
		Pair(int t, char dir){
		this.t =t;
		this.dir = dir;
		}
	}
	
	static class Pos{
		int x;
		int y;
		
		Pos(int x, int y){
			this.x =x;
			this.y = y;
		}
	}
	
	public static boolean cango(int x, int y) {
		
		return x>=0 && x<n && y>=0 && y<n;
	}
	
	public static void print() { //arr dump 코드
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				
				System.out.print(arr[i][j]+" ");
				
				
			}
			System.out.println();
		}
	}
	
	public static int simulate() {
		
		 
		
		LinkedList<Pos>snake = new LinkedList<>(); //링크드 리스트를 이용해서 뱀 몸의 위치저장
		snake.add(new Pos(0,0));
		arr[0][0]=2; //뱀은 2로 표시
		int dir =3; //오른쪽 방향
		int time =0;
		
		while(true) {
			
		
			
			time++; //시간 카운트
			Pos spos = snake.get(0);
			int nx = spos.x+dx[dir];
			int ny = spos.y+dy[dir];
			
			if(cango(nx,ny)) { //벽이 아니라 갈 수 있을때
				
				if(arr[nx][ny]==1) { //만약 사과가 있을떄
					
					snake.addFirst(new Pos(nx,ny)); //앞에만 늘려준다
					arr[nx][ny]=2; //늘려준 부분 2로저장
				}
				else if(arr[nx][ny]==0) {  // 사과가 없을때
					
					snake.addFirst(new Pos(nx,ny)); //앞에만 늘려준다
					arr[nx][ny]=2; //늘려준 부분 2로저장
					
					Pos epos = snake.get(snake.size()-1); //맨 뒤의 좌표 가져오기
					arr[epos.x][epos.y]=0; //맨 뒤에 부분 0으로 해준다
					snake.removeLast(); //맨뒤에 부분 없애주기
				}
				else if(arr[nx][ny]==2) { // 뱀이 자기자신을 만나면 멈춘다
					break;
				}
				
			}
			else { //벽일때 멈춘다
				
				break;
				
			}
			
			
			if(hm.containsKey(time)) {
				
				char c = hm.get(time);
				if(c=='L') {
					dir = (dir+3)%4; //오른쪽90도 회전하는 모듈러 연산
				}
				else if(c=='D') {
					
					dir=(dir+1)%4; //왼쪽 90도 회전하는 모듈러 연산
					
				}
				
				
			}
			
			
			
		}
		
		return time;
		
	}
	
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		k =Integer.parseInt(br.readLine());
		
		arr = new int[n][n];
		
		for(int i=0; i<k; i++) { //사과 배치하기
			
			st =new StringTokenizer(br.readLine());
			arr[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1]=1;
		}
		
		int l = Integer.parseInt(br.readLine()); 
		
		int sx = 0;
		int sy =0;
		
	
		
		for(int i=0; i<l; i++) {
			st =new StringTokenizer(br.readLine());
			hm.put(Integer.parseInt(st.nextToken()),st.nextToken().charAt(0));
		}
		
		System.out.println(simulate());
		
		
	}
	
	
}

- 어려웠던 점1: 오른족 90도-> (dir+1)%4 , 왼쪽 90도 ->(dir+3)%4

- 어려웠던 점2: 이문제에서는 뱀이 움직이는 방법을 쉽게 설명해줘서 빨리 구현할 수 있었지만 설명이 없다면 어려울것같다.