[알고리즘] 백준3190 뱀 - 자바

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

3190번: 뱀

 

 

[풀이 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_3190_뱀 {
	static int N, K, dir;
	static int[][] map;
	static int dy[] = {0, 1, 0, -1};
	static int dx[] = {1, 0, -1, 0};
	static Queue<DPoint> dp = new LinkedList<>();
	static Deque<Point> q = new ArrayDeque<>();
	int i, j;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		map = new int[N][N]; // 입력부터 귀찮아 갈 수 있는 곳은 0으로!
		
		K = Integer.parseInt(br.readLine());
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			map[y-1][x-1] = 1; // 사과는 1로 두기
		}
		
		K = Integer.parseInt(br.readLine());
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine());
			int sec = Integer.parseInt(st.nextToken());
			char move = st.nextToken().charAt(0);
			dp.add(new DPoint(sec, move));
		}// dp큐에 방향 변환 정보를 담기
		
		
		
		q.offer(new Point(0, 0)); //시작지점 넣어주기
		int i = 0, j = 0, sec = 0;
		
		while(true) {
			sec++;
			int y = i + dy[dir];
			int x = j + dx[dir];
			
			if(check(y, x)) // 벽이랑 몸통이랑 부딪히면 끝
				break;
			
			if(map[y][x] == 1) { // 앞에 사과라면
				map[y][x] = 0; // 와 설마 이거 안해줘서..? 맞네;
				q.offerLast(new Point(y, x));
			}else { // 사과가 아니라면
				q.offerLast(new Point(y, x)); // 머리 붙이기
				q.pollFirst(); // 꼬리 자르기
			}
			
			i = y;
			j = x; 
			
			if(!dp.isEmpty() && sec == dp.peek().sec) { // 비어있지 않고 현재 초와 입력받은 dp큐의 초가 같다면
				DPoint dpoint = dp.poll();
				if(dpoint.move == 'D') { // 오른쪽으로 가야한다면
					dir++;
					if(dir == 4) dir=0;
				}else { // 왼쪽으로 가야한다면
					dir--;
					if(dir == -1) dir = 3;
				}
			}
			
		}
		
		System.out.println(sec);
		
		
	}
	
	static boolean check(int y, int x) {
		if(y < 0 || x < 0 || y >= N || x >= N) {// 벽도 안부딪히고
			return true;
		}
		for(Point point : q) {
			if(y == point.y && x == point.x)
				return true;
		}
		return false;
	}
	
	static class Point{ // 좌표
		int y, x;
		Point(int y, int x){
			this.y = y;
			this.x = x;
		}
	}
	
	static class DPoint{ // 방향 변환 정보
		int sec;
		char move;
		DPoint(int sec, char move){
			this.sec = sec;
			this.move = move;
		}
	}
	
	

	
}

• 구현 문제.. 특히 삼성 SW 역량 기출문제들은 신경 쓸게 참 많은 것 같다. 그래도 재밌게 풀었던 문제
  
  
• 문제를 이해하는데 시간이 오래 걸렸는데 방향전환을 해줄 땐 내 머리가 아닌 뱀머리를 돌려야 된다. 내 입장에서 백날 돌리니 문제가 이해가 가지 않았다.. 뭐한 거지
  
  
• 벽이랑 몸통이랑 부딪히면 끝이 나기 때문에 따로 함수로 빼서 처리를 해주었다.
  
  
• 이어서 입력받은 맵에 사과가 있는 부분을 1로 해줬는데 사과를 먹으면 무조건 0으로 바꿔줘야 한다. 정말 당연한 건데 이 부분을 빼먹어서 애꿎은 시간만 버렸다.
  
  
• 이 문제의 핵심은 deque를 쓴다는 점과 뱀머리가 몸통에 닿을 때를 처리해주는 부분인 것 같다.