[백준] 3190: 뱀 (Java)

Yoon Uk·2022년 7월 28일
Java백준시뮬레이션알고리즘
0

알고리즘 - 백준

목록 보기
39/130
post-thumbnail
post-custom-banner

문제

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

풀이

조건

  • 뱀이 이동한다.
    • 머리가 먼저 이동한다.
    • 이동한 자리에 사과가 없다면 꼬리를 한 칸 당겨 뱀 길이가 일정해 지도록 한다.
    • 이동한 자리에 사과가 있다면 꼬리를 그대로 두어 뱀 길이가 한 칸 길어지도록 한다.
  • 뱀의 머리가 영역 밖으로 벗어나거나 자신의 몸에 닿이게 되면 종료한다.
  • 뱀의 초기 위치는 (1, 1)이고 초기 방향은 오른쪽이다.

풀이 순서

  • 좌표와 헷갈리지 않게 하기 위해 map 크기를 N+1로 해준다.
  • 사과의 위치에는 9를 넣어 준다.
  • HashMap을 이용하여 Key 값에 시간, Value 값에 방향값을 넣어준다.
  • 시간에 따라 while문이 돌도록 해주고 반복 1회가 1초 동안 일어나는 일이다.
  • 뱀의 머리가 방향에 맞춰 이동을 한다.
    • 뱀의 머리가 종료 조건에 해당하면 종료시킨다.
    • 뱀의 머리가 사과 위치로 왔다면 머리만 늘린다.
    • 뱀의 머리가 빈 칸으로 왔다면 머리를 늘리고 꼬리는 줄어들게한다.
  • 현재 시간을 Key 값으로 하는 Value 값이 있는지 확인하고 있다면 해당 Value 값을 방향으로 갱신해준다.

코드

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

public class Main {

	static int N; // 맵 크기
	static int K; // 사과 갯수
	static int L; // 명령 갯수
	static int time; // 답으로 낼 횟수
	static int[][] map;
	static ArrayList<int[]> snake; // 뱀의 몸통 좌표가 들어갈 리스트
	
	static int idx = 0; // 방향 찾을 때 쓸 인덱스 -> 처음엔 오른쪽을 보고 있음
	static int[] dx = {0, 1, 0, -1}; // 오른쪽 , 아래, 왼쪽, 윗쪽
	static int[] dy = {1, 0, -1, 0};
	
	static HashMap<Integer, Character> dir; // 이동 횟수와 방향 정보 넣을 맵
    
	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+1][N+1]; // 좌표값 안 헷갈리기 위해 N+1 해줌
		
		K = Integer.parseInt(br.readLine()); // 사과 갯수
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			map[r][c] = 9; // 사과 위치
		}
		
		// 뱀 방향 정보 입력
		dir = new HashMap<>(); // 이동 횟수와 방향 정보 넣을 맵
		L = Integer.parseInt(br.readLine());
		for(int i=0; i<L; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int moveCnt = Integer.parseInt(st.nextToken()); // 이동 횟수
			char turnDir = st.nextToken().charAt(0); // 방향 정보
			
			dir.put(moveCnt, turnDir);
		}
		
		// 뱀 시작
		snake = new ArrayList<>(); // 뱀 몸통 넣을 리스트
		snake.add(new int[] {1, 1}); // 처음엔 (1, 1)위치에 있기 때문에 넣어줌
		
		time = 0;
		int nx, ny; // 새롭게 이동한 위치
		int thisX, thisY; // 현재 위치
		thisX = 1;
		thisY = 1;
		
		while(true) {
			time++; // 반복문이 반복 되는 것이 수행한 횟수
			
			nx = thisX + dx[idx]; // 바라보는 방향으로 머리 좌표 이동
			ny = thisY + dy[idx]; // 바라보는 방향으로 머리 좌표 이동
			
			if(isFinish(nx, ny)) break; // 종료 조건이 되면 while문 탈출
			
			// 사과를 만나면
			if(map[nx][ny] == 9) {
				map[nx][ny] = 0; // 사과 자리는 0으로 바꿔줌
				snake.add(new int[] {nx, ny}); // 뱀 머리만 넣어줌
			} 
			// 사과가 없는 자리라면
			else {
				snake.add(new int[] {nx, ny}); // 벰 머리 넣어줌
				snake.remove(0); // 꼬리는 없애서 몸 길이를 일정하게 유지해 줌
			}
			
			thisX = nx; // 현재 위치 갱신
			thisY = ny; // 현재 위치 갱신
			
			// 현재 time을 key값으로 가진 값이 존재한다면
			if(dir.containsKey(time)) {
				// 해당 key 값의 value가 D라면
				if(dir.get(time) == 'D') {
					idx++;
					if(idx == 4) idx = 0;
				}
				// 해당 key 값의 value가 L이라면
				if(dir.get(time) == 'L') {
					idx--;
					if(idx == -1) idx = 3;
				}
			}
		}
		
		System.out.println(time);
		
	}
	
	// 끝나는 조건이면 true 반환
	static boolean isFinish(int x, int y) {
		// map 범위 벗어났는지 체크
		if(x < 1 || y < 1 || x > N || y > N) return true;
		
		// 뱀의 몸통과 머리가 만났는지 체크
		for(int i=0; i<snake.size(); i++) {
			if(x == snake.get(i)[0] && y == snake.get(i)[1]) {
				return true;
			}
		}
		
		return false;
	}
	
}

처음에 했던 틀린 풀이

풀이 순서

  • 뱀의 몸이 있는 칸은 1을 넣어준다.
  • 뱀의 머리가 새롭게 도달한 위치에 1을 넣어준다.
    • 해당 위치에 사과가 있었다면 꼬리를 줄여주지 않는다.
    • 해당 위치에 사과가 없었다면 꼬리를 줄여준다.
      • 이 때 꼬리의 다음 위치가 뱀의 몸인 1이 아니라면 방향을 머리의 방향과 맞춰주고 이동시킨다.
      • 꼬리의 다음 위치가 뱀의 몸인 1이라면 해당 방향으로 꼬리를 당겨주고 원래 있었던 꼬리의 위치에는 0을 넣어준다.

코드

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

public class Main {
	
	static int N;
	static int ans; // 답
	static int[][] map;
	static char headDir, tailDir; // 머리와 꼬리의 방향
	static int headX, headY;
	static int tailX, tailY;
	
	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];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = 0;
			}
		}
		
		map[0][0] = 1; // 뱀의 초기 위치 -> 뱀이 있는 위치에는 1을 넣어줌
		
		int K = Integer.parseInt(br.readLine()); // 사과 갯수
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			map[r-1][c-1] = 9; // 사과 위치
		}
		
		int L = Integer.parseInt(br.readLine()); // 뱀의 방향 전환 횟수
		
		headDir = 'E'; // 머리의 초기 방향
		tailDir = 'E'; // 꼬리의 초기 방향
		// 머리의 초기 위치
		headX = 0;
		headY = 0;
		// 꼬리의 초기 위치
		tailX = 0;
		tailY = 0;
		for(int i=0; i<L; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int x = Integer.parseInt(st.nextToken()); // 게임 시작 후 x초
			char c = st.nextToken().charAt(0); // 회전 방향
			
			// 직진 횟수 만큼 반복
			for(int j=0; j<x; j++) {
				ans++;
				
				// 머리가 앞으로 한 칸 감
				headMove(headDir);
				
				// 종료 조건 -> 범위를 벗어나거나 머리가 몸에 닿임
				if(headX < 0 || headY < 0 || headX >= N || headY >= N || map[headX][headY] == 1) {
					System.out.println(ans);
					return;
				}
				
				// 앞으로 간 머리가 사과를 만나면
				if(map[headX][headY] == 9) {
					// 사과 자리를 1로 바꾸고 꼬리는 움직이지 않고 다음 반복문으로 넘김
					map[headX][headY] = 1;
					continue;
				} else { // 앞으로 간 머리가 그냥 빈 칸 일 때
					// 해당 자리에 1을 넣음
					map[headX][headY] = 1;
					// 꼬리가 있었던 자리는 0으로 바꿈
					map[tailX][tailY] = 0;
					// 꼬리가 몸 따라서 잘 가는지 체크
					if(!checkNextTail(tailDir, tailX, tailY)) {
						// 꼬리의 방향을 머리의 방향과 맞춰줌
						tailDir = headDir;
					}
					// 꼬리 한 칸 움직임
					tailMove(tailDir);		
				}
	
			}
			// 머리 방향 바꾸는 명령
			headDir = changeDir(headDir, c);
			
		}
		
	}
	 // 머리의 방향대로 이동
	static void headMove(char nowDir) {
		switch(nowDir) {
			case 'E': headY++;
				break;
				
			case 'S': headX++;
				break;
				
			case 'W': headY--;
				break;
				
			case 'N': headX--;
				break;
				
			default:
				break;
		}
	}
	
	// 꼬리의 방향대로 이동
	static void tailMove(char nowDir) {
		switch(nowDir) {
			case 'E': tailY++;
				break;
				
			case 'S': tailX++;
				break;
				
			case 'W': tailY--;
				break;
				
			case 'N': tailX--;
				break;
				
			default:
				break;
		}
	}
	
	// 꼬리의 방향과 머리의 방향이 같다면 true 반환
	static boolean checkNextTail(char tailDir, int nowTailX, int nowTailY) {
		
		switch(tailDir) {
			case 'E': nowTailY++;
				break;
				
			case 'S': nowTailX++;
				break;
				
			case 'W': nowTailY--;
				break;
				
			case 'N': nowTailX--;
				break;
				
			default:
				break;
		}
		
		if(map[nowTailX][nowTailY] == 1) {
			return true;
		} else if(map[nowTailX][nowTailY] == 0) {
			return false;
		}
		
		return false;
	}
	
	// 명령에 따라 방향 바꾸기
	static char changeDir(char now, char order) {
		char postHead = ' ';
		
		switch(now) {
			case 'E': 
				if(order == 'L') {
					postHead = 'N';
				} else if(order == 'D') {
					postHead = 'S';
				}
				break;
				
			case 'S':
				if(order == 'L') {
					postHead = 'E';
				} else if(order == 'D') {
					postHead = 'W';
				}
				break;
				
			case 'W':
				if(order == 'L') {
					postHead = 'S';
				} else if(order == 'D') {
					postHead = 'N';
				}
				break;
				
			case 'N':
				if(order == 'L') {
					postHead = 'W';
				} else if(order == 'D') {
					postHead = 'E';
				}
				break;
				
			default:
				break;
		}
		
		return postHead;
	}
}

정리

  • 처음 풀이를 했을 때 입력 받는 조건에 대해 이해를 잘 못 해서 틀렸었다.
  • 적절한 자료구조를 이용하면 풀이가 더 쉬워진다.
profile
Yoon Uk
이전 포스트

[백준] 16236: 아기 상어 (Java)

다음 포스트

[백준] 1987: 알파벳 (Java)

post-custom-banner

0개의 댓글