본문으로 바로가기

BOJ#3190 뱀

category Algorithm BOJ/시뮬레이션 2017. 4. 15. 11:56

BOJ#3190 뱀


* 문제


* 풀이

map과 direction 2차원 배열을 선언하였습니다.

map이 가질 수 있는 값 : 0(빈칸), 1(뱀), 2(사과)

direction이 가질 수 있는 값 : 상, 하, 좌, 우
→ 각 위치(row, col)에서 머리 또는 꼬리가 어느 방향으로 이동해야 하는지 알기 위함

시뮬레이션 진행 알고리즘은 아래와 같고, 중간 중간에 map과 direction 정보를 업데이트해서 답을 찾을 수 있게 하였습니다.

머리 이동

 - 맵을 벗어난 경우
  - 종료

 - 빈칸인 경우
  - 꼬리 이동

 - 사과인 경우
  - None

 - 뱀인 경우
  - 종료

↓ 테스트 케이스 보기 (클릭) ↓


* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%233190_Snake/src/Main.java


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

public class Main {

static int[][] map = new int[102][102];
static int[][] direction = new int[102][102];

static final int[] dRow = {0, -1, 0, 1};
static final int[] dCol = {-1, 0, 1, 0};

//static final int LEFT = 0;
//static final int UP = 1;
static final int RIGHT = 2;
//static final int DOWN = 3;

static final int BLANK = 0;
static final int SNAKE = 1;
static final int APPLE = 2;

static final int INF = 100;

public static void main(String[] args) throws IOException {

int N; // map size
int K; // apple
int L; // 뱀의 방향 변환 개수
int headRow = 1, headCol = 1; // 머리 위치
int tailRow = 1, tailCol = 1; // 꼬리 위치
int curDir = RIGHT; // 머리 방향

// input - 맵 정보(맵 크기, 사과)
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

N = Integer.parseInt(br.readLine());
K = Integer.parseInt(br.readLine());

for (int i = 0; i < K; i++) {

StringTokenizer st = new StringTokenizer(br.readLine());

map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = APPLE;
}

// input - 뱀 이동정보
L = Integer.parseInt(br.readLine());

MoveInfo[] info = new MoveInfo[L + 1];
for (int i = 0; i < L; i++) {

StringTokenizer st = new StringTokenizer(br.readLine());

info[i] = new MoveInfo(Integer.parseInt(st.nextToken()), st.nextToken().charAt(0));
}
info[L] = new MoveInfo(INF, 'D');

// solve
// 초기 위치
map[headRow][headCol] = SNAKE;
direction[headRow][headCol] = curDir;

int step = 0;
boolean ret = false;

// 뱀 이동 시작
for (int i = 0; i < L + 1 && !ret; i++) {

// 뱀 이동 정보를 차례로 꺼내오기
int X = info[i].time;
char C = info[i].rotateDir;

// 시간 차이만큼 이동
int diff = X;
if (i > 0) diff = info[i].time - info[i - 1].time;

while (diff-- > 0) {

step++;

// 맵 위치에 방향 기록
direction[headRow][headCol] = curDir;

// 머리 이동
headRow += dRow[curDir];
headCol += dCol[curDir];

// 종료 - 벽에 충돌한 경우
if (headRow < 1 || headRow > N || headCol < 1 || headCol > N) {

System.out.println(step);
ret = true;
break;
}

// 진행 - 빈칸인 경우
if (map[headRow][headCol] == BLANK) {

// 맵업데이트
map[headRow][headCol] = SNAKE;
direction[headRow][headCol] = curDir;

map[tailRow][tailCol] = BLANK;

// 꼬리 이동
int tailDir = direction[tailRow][tailCol];
tailRow += dRow[tailDir];
tailCol += dCol[tailDir];
}

// 진행 - 사과를 만난 경우
else if (map[headRow][headCol] == APPLE) {

// 맵 업데이트
map[headRow][headCol] = SNAKE;
direction[headRow][headCol] = curDir;
}

// 종료 - 자기 자신을 만난 경우
else if (map[headRow][headCol] == SNAKE) {

System.out.println(step);
ret = true;
break;
}
}

// 방향 갱신
curDir = C == 'L' ? (curDir - 1 + 4) % 4 : (curDir + 1) % 4;

} // ~ for loop
} // ~ main
}

class MoveInfo {

int time;
char rotateDir;

MoveInfo(int time, char rotateDir) {

this.time = time;
this.rotateDir = rotateDir;
}
}

class Point {

int row, col;

Point(int row, int col) {

this.row = row;
this.col = col;
}
}


'Algorithm BOJ > 시뮬레이션' 카테고리의 다른 글

BOJ#11559 Puyo Puyo  (0) 2017.09.21
BOJ#14503 로봇 청소기  (0) 2017.04.22
BOJ#3190 뱀  (5) 2017.04.15
BOJ#2931 가스관  (1) 2017.04.14
BOJ#10875 뱀  (0) 2017.04.14
BOJ#14499 주사위 굴리기  (1) 2017.04.11

댓글을 달아 주세요

  1. nammink 2017.07.29 18:10

    안녕하세요 혹시 1312 가 나와야 하는 테스트 케이스에서는 어떤 예외처리를 해줘야 하는지 알 수 있을까요?

    저 값만 다르게 나오네요

    감사합니다~!

    • BlogIcon stack.07142 2017.07.31 16:02 신고

      안녕하세요! 댓글을 늦게 봤네요
      저 테스트 케이스만 봐서는 어떤 예외처리가 필요한지 판단 할 수 없을것 같아요

      시뮬레이션 문제니까
      저 테스트 케이스에 대해서 step by step으로 디버깅 해보시면 될 것 같습니다.

      혹시 도움이 더 필요하시면 댓글 남겨 주세요.
      감사합니다

  2. sryu 2017.10.20 18:43

    8
    3
    5 4
    5 8
    2 5
    6
    7 D
    11 D
    15 D
    18 D
    19 D
    20 D
    이 케이스가 계속 안되서 생각해보니 주어진 회전 시간이 지나서 종료되는 경우를 생각안햇더라구요... 배열 L번째에 저렇게 넣으면 되네요! 하다가 잘 안되서 검색해봤는데 좋은 풀이 감사합니다 !!

  3. minsup90 2020.01.14 00:05

    좋은 정보 감사합니다. 죄송하지만 테스트케이스 같은경우 어디서 구하는지 알수 있을까요? 대부분은 인터넷 있지만, 검색해도 없는 경우가 있기에 구하는 따로 구하는 경로가 있으신가요?