[ 백준 3190 뱀 ] 문제 풀이(Java) - 삼성 SW역량테스트 기출

백준 3190번 뱀 문제를 풀어보았습니다.

 

해당 문제는 시뮬레이션 문제로 큐를 이용하면 간단하게 풀 수 있는 문제였습니다.

 

 

문제보기

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

3190번: 뱀

 

나의 풀이

 

주어진 조건대로 구현하면 되는 문제입니다!

 

아래 조건을 만족하도록 구현을 하면 되는데요, 

 

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

 

일단 뱀을 나타내기 위해 Queue를 사용했습니다. 현재 뱀이 위치한 칸을 Queue에 저장하고 매 초가 지날 때마다 뱀의 머리에 해당하는 부분을 add 해주고 꼬리를 비워주고 하는 식으로 구현했습니다.

 

그래서 time을 1씩 증가시키면서 무한푸트를 돌되 무한 루프 탈출 조건은 뱀의 다음 머리 위치가 배열의 크기를 벗어나는 경우와 다음 위치가 현재 뱀의 몸이 위치한 곳인 경우로 잡아주었습니다!

 

뱀의 몸이 위치한 곳을 효율적으로 찾기 위해 저는 배열에 현재 뱀의 몸이 위치한 곳은 2로 나타내어 주었습니다.

(0: 빈 칸, 1: 사과가 위치한 곳, 2: 뱀이 위치한 곳)

 

 

코드

 

//시뮬레이션 문제

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

public class N_3190 {
	static class Turn{    //방향 전환 정보
		int time;
		char dir;
		
		Turn(int time, char dir){
			this.time = time;
			this.dir = dir;
		}
	}
	
	static class Point{
		int i;
		int j;
		
		Point(int i, int j){
			this.i = i;
			this.j = j;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			int N = Integer.parseInt(br.readLine());
			int K = Integer.parseInt(br.readLine());
			
			int [][] A = new int[N][N];
			for(int i=0;i<K;i++) {   //사과의 위치 저장
				String [] arr = br.readLine().split(" ");
				A[Integer.parseInt(arr[0]) - 1][Integer.parseInt(arr[1]) - 1] ++;
			}
			
			int L = Integer.parseInt(br.readLine());
			Queue<Turn> q = new LinkedList<Turn>();    //방향 전환 정보 저장
			
			for(int i=0;i<L;i++) {
				String [] arr = br.readLine().split(" ");
				q.offer(new Turn(Integer.parseInt(arr[0]), arr[1].charAt(0)));
			}
			
			LinkedList<Point> snake = new LinkedList<Point>();     //뱀이 위치한 칸들 저장
			int snake_dir = 4;       //뱀의 현재 방향(1: 상, 2: 하, 3: 좌, 4: 우)
			snake.add(new Point(0, 0));
			A[0][0] = 2;     //보드에 뱀의 위치 표시
			int time = 0;
			
			
			while(true) {
				time++;
				
				if(snake_dir == 1) {
					if(snake.get(0).i - 1 < 0 || A[snake.get(0).i - 1][snake.get(0).j] == 2) break;
					
					if(A[snake.get(0).i-1][snake.get(0).j] == 1) {    //이동한 칸에 사과가 잇다면
						A[snake.get(0).i-1][snake.get(0).j] = 2;
						snake.add(0, new Point(snake.get(0).i-1, snake.get(0).j));
						
					}else {
						A[snake.get(0).i-1][snake.get(0).j] = 2;
						snake.add(0, new Point(snake.get(0).i-1, snake.get(0).j));
						A[snake.get(snake.size()-1).i][snake.get(snake.size()-1).j] = 0;
						snake.remove(snake.size()-1);
					}
				}else if(snake_dir == 2) {
					if(snake.get(0).i + 1 >= N || A[snake.get(0).i + 1][snake.get(0).j] == 2) break;
					
					if(A[snake.get(0).i+1][snake.get(0).j] == 1) {    //이동한 칸에 사과가 잇다면
						A[snake.get(0).i+1][snake.get(0).j] = 2;
						snake.add(0, new Point(snake.get(0).i+1, snake.get(0).j));
						
					}else {
						A[snake.get(0).i+1][snake.get(0).j] = 2;
						snake.add(0, new Point(snake.get(0).i+1, snake.get(0).j));
						A[snake.get(snake.size()-1).i][snake.get(snake.size()-1).j] = 0;
						snake.remove(snake.size()-1);
					}
				}else if(snake_dir == 3) {
					if(snake.get(0).j - 1 < 0 || A[snake.get(0).i][snake.get(0).j - 1] == 2) break;
					
					if(A[snake.get(0).i][snake.get(0).j - 1] == 1) {    //이동한 칸에 사과가 잇다면
						A[snake.get(0).i][snake.get(0).j - 1] = 2;
						snake.add(0, new Point(snake.get(0).i, snake.get(0).j-1));
						
					}else {
						A[snake.get(0).i][snake.get(0).j-1] = 2;
						snake.add(0, new Point(snake.get(0).i, snake.get(0).j-1));
						A[snake.get(snake.size()-1).i][snake.get(snake.size()-1).j] = 0;
						snake.remove(snake.size()-1);
					}
				}else if(snake_dir == 4) {
					if(snake.get(0).j + 1 >= N || A[snake.get(0).i][snake.get(0).j + 1] == 2) break;
					
					if(A[snake.get(0).i][snake.get(0).j + 1] == 1) {    //이동한 칸에 사과가 잇다면
						A[snake.get(0).i][snake.get(0).j + 1] = 2;
						snake.add(0, new Point(snake.get(0).i, snake.get(0).j+1));
						
					}else {
						A[snake.get(0).i][snake.get(0).j+1] = 2;
						snake.add(0, new Point(snake.get(0).i, snake.get(0).j+1));
						A[snake.get(snake.size()-1).i][snake.get(snake.size()-1).j] = 0;
						snake.remove(snake.size()-1);
					}
				}
				
				if(q.size() > 0 && q.peek().time == time) {
					Turn t = q.poll();
					
					if(t.dir == 'D') {
						
						if(snake_dir == 1)
							snake_dir = 4;
						else if(snake_dir == 2)
							snake_dir = 3;
						else if(snake_dir == 3)
							snake_dir = 1;
						else if(snake_dir == 4)
							snake_dir = 2;
						
					}else if(t.dir == 'L') {
						if(snake_dir == 1)
							snake_dir = 3;
						else if(snake_dir == 2)
							snake_dir = 4;
						else if(snake_dir == 3)
							snake_dir = 2;
						else if(snake_dir == 4)
							snake_dir = 1;
					}
					
				}
			}
			
			System.out.println(time);
		}catch(IOException e) {
			e.printStackTrace();
		}
	}

}

 

결과

 

백준 채점결과!