https://www.acmicpc.net/problem/3190
3190번: 뱀
문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
www.acmicpc.net
문제
해결 방안
문제 전체 다 꼼꼼히 읽어봐야하는 Simulation(구현) 문제이다.
먼저 크게 1. 전체 입력 받는 부분 2. 게임 돌아가는 부분 두 가지로 나누어서 생각을 해봤다.
1. 전체 입력 받는 부분
1-1 보드의 크기
사과의 위치가 행, 열 그대로 주어져서 N+1 x N+1로 설정하였다.
1-2 사과의 위치
보드 위치 위에 사과가 있는 경우 1을 저장해주었다. (board[row][col] = 1)
1-3 뱀의 방향 정보
HashMap 자료구조를 이용하여 key에 시간을 넣어주고 value에 방향값을 넣어줘서 나중에 key값이 있는지 쉽게 찾을 수 있게 하였다.
2. 뱀 게임이 돌아가는 부분
시간에 따른 반복문을 돌게 하였다. 즉 while 안은 1초동안 이뤄지는 일들이다.
index 값을 이용하여 뱀의 머리가 진행할 방향을 설정해주었다.
초깃값은 index=0으로 오른쪽 방향이다.(dx[0], dy[0])
index=0 오른쪽 // index=1 아래 // index=2 왼쪽 //index=3 위
2-5에서 오른쪽으로 방향을 틀면 index++ 이고 왼쪽으로 방향을 틀면 index--가 될것이다.
2-1 다음 움직임 설정
nx, ny를 이용하여 현재 위치에 머리가 진행할 방향으로 이동해준다.
nx = cx + dx[index]
ny = cy + dy[index]
2-2 다음 움직임에 따른 게임이 끝나는지 확인
2-2-1 nx, ny가 벽에 부딪히는 경우(범위 넘어가는 경우)를 확인해준다.
2-2-2 nx, ny가 자기 몸통에 부딪힌 경우를 확인해준다.(snake 몸통 정보 확인)
2-3 보드에 사과 유무에 따른 일 수행
2-3-1 사과 있을 때 머리만 늘어난다.
2-3-2 사과 없을 때 머리는 늘어나고 꼬리는 줄어든다.
2-4 현재 움직임에 다음 움직임 저장
2-5 뱀의 방향 이동 정보가 있는지 확인하고 있으면 방향 설정
해당 시간이 HashMap key값에 있는지 확인하고 방향을 새로 설정해준다.
자세한 것은 코드 주석과 비교하며 코드를 참고하면 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
// 뱀
// NxN 정사각형 보드
// 맨위 맨 위측 위치(1,1), 처음 오른쪽 방향을 향함
// 뱀은 계속 머리쪽이 늘어남
// 사과 있으면 사과 없어지고 머리 늘려서 꼬리 그대로
// 사과 없으면 머리 늘려서 꼬리가 위치한 칸 비워줌
public class Main {
static int n; // 보드의 크기 (2~100)
static int k; // 사과의 갯수 (0~100)
static int l; // 뱀의 방향 변환 횟수 (1~100)
static int time; // 게임 시간
static int[][] board;
static List<int[]> snake; //뱀의 몸통 위치 (x,y)
// 처음 시작은 오른쪽 방향을 보고 있음
// 0:오른쪽 1:아래쪽 2:왼쪽 3:위
// D(오른쪽)가 다오면 index++
// L(왼쪽)이 나오면 index--
static int index = 0;
static int[] dx = {0, 1, 0, -1}; //세로
static int[] dy = {1, 0, -1, 0}; //가로
static Map<Integer, String> dir; // 뱀의 방향 정보
public static void main(String[] args) throws Exception, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
k = Integer.parseInt(br.readLine());
// 1,1이 맨 위 맨 좌측
board = new int[n+1][n+1];
// 사과 위치 입력
String str;
int row; // 행
int col; // 열
for(int i=0; i<k; i++) {
str = br.readLine();
row = Integer.parseInt(str.split(" ")[0]);
col = Integer.parseInt(str.split(" ")[1]);
board[row][col] = 1;
}
// 뱀 방향 정보 입력
dir = new HashMap<>();
l = Integer.parseInt(br.readLine());
for(int i=0; i<l; i++) {
str = br.readLine();
int timeInfo = Integer.parseInt(str.split(" ")[0]);
String directionInfo = str.split(" ")[1];
dir.put(timeInfo, directionInfo);
}
// 뱀 시작 지점 (1,1) (x,y)
snake = new LinkedList<>();
snake.add(new int[]{1,1});
time = 0;
int nx, ny; // 다음 움직임
int cx, cy; // 현재 움직임(1,1)
cx = 1;
cy = 1;
// 뱀 움직임 시작
while(true) {
time++;
// 다음 움직임(머리 데이터)
nx = cx + dx[index];
ny = cy + dy[index];
// 끝나는지 확인
if(isFinish(nx,ny)) break;
// 사과 있는지 확인
// 사과 있으면 사과 없어지고 머리 늘려서 꼬리 그대로
if(board[nx][ny] == 1) {
board[nx][ny] = 0;
snake.add(new int[] {nx,ny}); // 머리 정보 추가
}
// 사과 없으면 머리 늘려서 꼬리가 위치한 칸 비워줌
else {
snake.add(new int[] {nx,ny}); // 머리 정보 추가
snake.remove(0); // 꼬리 index는 0
}
cx = nx;
cy = ny;
// 해당 시간 끝났을 때 다음 방향 정해주기
if(dir.containsKey(time)) {
// D(오른쪽)가 다오면 index++
if(dir.get(time).equals("D")) {
index++;
if(index == 4)
index = 0;
}
// L(왼쪽)이 나오면 index--
if(dir.get(time).equals("L")) {
index--;
if(index == -1)
index = 3;
}
}
}
System.out.println(time);
}
// 게임이 끝나는지 확인
static boolean isFinish(int nx, int ny){
// 벽에 부딪히거나
if(nx<1 || ny<1 || nx>=n+1 || ny>=n+1)
return true;
// 자기 몸통에 닿거나
for(int i=0; i<snake.size(); i++) {
if(nx == snake.get(i)[0] && ny == snake.get(i)[1])
return true;
}
return false;
}
}
'Old > Algorithms' 카테고리의 다른 글
| [JAVA] 백준 14501번 : 퇴사 (삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.15 |
|---|---|
| [JAVA] 백준 12100번 : 2048 (Easy) (삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.12 |
| [JAVA] 백준 14500번 : 테트로미노 (삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.10 |
| [JAVA] 백준 14499번 : 주사위 굴리기 (삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.07 |
| [JAVA] 백준 13458번 : 시험 감독 (삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.06 |
