[백준] 3190 - 뱀 (JAVA)

1. 소요시간 : 59분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 구현, 자료 구조, 시뮬레이션, 덱, 큐
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/3190
8. 푼 날짜 : 2023.04.04

1. 사용한 자료구조 & 알고리즘

큐, 해시맵, 구현.

2. 사고과정

걸린시간은 59분 이지만 2일 전쯤 30분 시도하다 못 푼것 감안해야 할듯 !

일단 이 문제는 문제 설명을 좀 이상하게 한 것 같다.
문제 이해가 안 돼서 어떤 방식으로 뱀이 이동하는지 검색한 뒤 문제를 이해했다.

가장 오래 고민한 것은 뱀이 이동할 때 어떻게 이동하는지이다.
방향을 전환하는 것은 금방 했는데, 꼬리는 우측으로 가고, 몸통은 아래로 가고, 머리는 왼쪽으로 갈 수도 있었다.
🧐 그래서 처음엔 각각 모든 좌표마다 left, right, up, down을 지정해줘야 생각하다가 얼마 뒤 깨달았다.
FIFO 방식을 사용해야 한다.

이 과정에서 queue를 사용했다. 선입선출 (FIFO) 를 따르고 있기 때문이다.

이것 하나를 깨닫고 나니 나머지는 쉬웠다.

3. 풀이과정

1. 사과의 위치를 저장.
2. 몇초에 어느쪽으로 방향이 바뀌는지 저장할 HashMap을 사용
3. 초기 위치 0,0 에 뱀을 놓음. 방향은 우측
4. 만약 해당 시간대에 방향을 바꾼다면, 현재 내가 상,하,좌,우 어디를 가고 있었는지에 따라서 다르게 바꿔줌.
   ex) 내가 우측으로 가고 있었고, 방향을 우측으로 튼다면 아래 방향으로 가는 것이 됨.
5. 방향에 따라서 좌표값을 변경해줌.
6. 해당 좌표가 맵의 index 값을 벗어나면 count 를 return
7. 해당 위치에 몸통이 존재한다면 count 를 return
8. 나머지 잡다한 부분은 코드에..

4. 소스코드

import java.util.*;
import java.io.*;

public class Main{
	static boolean apple[][];
	static boolean body[][];
	static HashMap<Integer,Character> second=new HashMap<>();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		
		int N=Integer.parseInt(br.readLine());
		int M=Integer.parseInt(br.readLine());
		apple=new boolean[N][N];
		body=new boolean[N][N];
		
		for(int i=0;i<M;i++) {
			st=new StringTokenizer(br.readLine());
			int n1=Integer.parseInt(st.nextToken());
			int n2=Integer.parseInt(st.nextToken());
			apple[n1-1][n2-1]=true;
		}
		
		int L=Integer.parseInt(br.readLine());
		for(int i=0;i<L;i++) {
			st=new StringTokenizer(br.readLine());
			int num=Integer.parseInt(st.nextToken());
			char move=st.nextToken().charAt(0);
			second.put(num+1,move);
			//몇 초에 좌,우 중 어느 방향으로 진행방향을 바꿀 것인지를 저장.
		}
		
		int result=snake();
		System.out.println(result);

		
	}
	public static int snake() {
		
		Queue<Moving> queue=new LinkedList<>();
		
		//가장 처음에 방문했던 곳이 지워짐. 그를 저장할 queue.
		Queue<Integer[]> removeList =new LinkedList<>();
		removeList.add(new Integer[] {0,0});
		
		//현재 0,0 좌표에 뱀이 있음
		body[0][0]=true;		
		
		queue.add(new Moving(0,0,0,1));
		while(!queue.isEmpty()) {
			Moving now=queue.poll();
			int nowY=now.y;
			int nowX=now.x;
			int dir=now.direction;
			int count=now.count;
			
			//해당 시간에 이동 방향을 바꾼다면
			if(second.containsKey(count)) {
				//어느 방향으로 바꿀지
				char nextDir=second.get(count);
				switch(dir) {
				//0은 오른쪽, 1은 왼쪽, 2는 위, 3은 아래
				case 0: dir= nextDir=='L'?2:3; break;
				case 1: dir= nextDir=='L'?3:2; break;
				case 2: dir= nextDir=='L'?1:0; break;
				case 3: dir= nextDir=='L'?0:1; break;
	
				}
			}
			//방향에 따라서 다음 좌표를 정함
			switch(dir) {
			case 0: nowX++; break;
			case 1: nowX--; break;
			case 2: nowY--; break;
			case 3: nowY++; break;
			}
			
			// 맵의 크기 벗어날 시 return
			if(nowX<0||nowY<0||nowX>=apple.length||nowY>=apple.length) 
				return count;
			
			//해당 좌표에 뱀의 몸이 있을 경우 return
			if(body[nowY][nowX])
				return count;
			
			//해당 좌표에 사과가 있다면 사과를 없애줌
			if(apple[nowY][nowX]) 
				apple[nowY][nowX]=false;
			
			//사과가 없다면 꼬리에 해당하는 맵의 body를 비워줌
			else {
				Integer last[]=removeList.poll();
				body[last[0]][last[1]]=false;
			}
		
			// 현재 위치를 저장.
			removeList.add(new Integer[] {nowY,nowX});
			body[nowY][nowX]=true;
			
			//count 늘려서 계속 탐색
			queue.add(new Moving(nowY,nowX,dir,count+1));
			
			
		}
		
		return -1;
		
	}
}

class Moving {
	int y;
	int x;
	int direction;
	int count;
	Moving(int y,int x,int direction,int count) {
		this.y=y;
		this.x=x;
		this.direction=direction;
		this.count=count;
	}
}

5. 결과

6. 회고

구현 문제 처음 풀 때는 재미 없었는데
계속 풀다보니까 은근 재밌다.
그래프 이론 문제처럼 유형만 어느정도 비슷한 ctrl C + ctrl V 문제가 아니라 진짜 내가 상상해서 구현해야 하기 때문이다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212