[java,백준3190]뱀 - Deque를 활용한 뱀 이동 시뮬레이션

Deque 자료구조를 활용하여 뱀의 머리와 꼬리를 동시에 관리하며 이동을 시뮬레이션하는 문제입니다.

뱀(백준3190)


예시를 시각화 해보자

문제 1번 예시 시각화:
1초
[0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 0, 0]
[0, 0, 0, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]

...

5초
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 2, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]

...

8초
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 2, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]

9초 => 답



풀이

구현 시 주의사항

💡 뱀의 머리와 꼬리 이동을 동시에 처리해야 하는 자료구조를 생각하고, 방향 전환 시점을 정확히 체크해야 한다.
Deque로 뱀의 머리와 꼬리를 관리하고, 매 초마다 이동과 방향 전환을 처리

💡 항상 시뮬레이션 문제는 “디버깅 강추!”


핵심 구현 사항

  • Deque를 사용한 뱀 관리 (머리, 꼬리 위주)
  • 사과 먹기 처리
  • 방향 전환 처리
  • 충돌 체크 (벽, 자기자신)


뱀 이동 처리

  1. nx<0||ny<0||nx>N-1||ny>N-1: 충돌체크 - 벽 부딪

  2. map[nx][ny]==1: 충돌체크 - 뱀 몸 부딪

  3. 사과 유무 분기??

    1. if map[nx][ny] == 2: 사과 있다면??

      checkDir(time, head, qu); 처리 이후에 머리이동, 꼬리 그대로 로직 사용

    2. else : 사과 없다면?

      checkDir(time, head, qu); 처리 이후에 머리이동, 꼬리 1칸 제거 로직 사용

static void solve(Queue<Info> qu) {
    Deque<Pair> dq = new ArrayDeque<>();
	map[0][0] = 1;
    dq.offer(new Pair(0, 0, 0));
    while (true) {
        // 머리 이동
        Pair head = dq.peekFirst();
        Pair tail = dq.peekLast();
        int nx = head.x + dx[head.dir];
        int ny = head.y + dy[head.dir];
        
        // 충돌 체크
        if(nx<0||ny<0||nx>N-1||ny>N-1) break; //벽 부딪
        if(map[nx][ny]==1) break; //뱀 몸에 부딪
        
        // 이동 처리
        if (map[nx][ny] == 2) {  // 사과가 있는 경우
			//(중요)방향 전환 있나 체크 후 추가(dir 수정)
			int dir = checkDir(time, head, qu);
            map[nx][ny] = 1;
            dq.offerFirst(new Pair(nx, ny, dir));
        } else {  // 사과가 없는 경우
            //(중요)방향 전환 있나 체크 후 추가(dir 수정)
            map[tail.x][tail.y] = 0;
            dq.pollLast();
			int dir = checkDir(time, head, qu);
            map[nx][ny] = 1;
            dq.offerFirst(new Pair(nx, ny, dir));
        }
    }
}


방향 전환 처리

  1. dir은 0~3 사이의 값을 가지기 때문에 해당 사이의 값을 가지게 로직을 구성
  2. 큐 제거로 null 에러 발생 방지 위해 main함수에서 qu.offer(new Info(9999999, 'X')); 필수
private static int checkDir(int time, Pair head, Queue<Info> qu) {
    Info info = qu.peek();
    int dir = head.dir;
    if (info.x == time) {
      if(info.c=='D') dir = (dir+1)%4;
      if (info.c == 'L') {
        if(dir-1 < 0) dir = 3;
        else dir = dir-1;
      }
	  qu.poll(); //큐 제거
    }
    return dir;
}



전체 코드

public class 뱀_3190 {
  static int N, K, L;
  static int[][] map; //약속 - 빈공간:0, 뱀:1, 사과:2
  static int[] dx = {0, 1, 0, -1};
  static int[] dy = {1, 0 ,-1, 0};
  static int result;

  static void solve(Queue<Info> qu) {
    //init
    Deque<Pair> dq = new ArrayDeque<>();
    int time = 0;
    map[0][0] = 1;
    dq.offer(new Pair(0, 0, 0));
    //run
    while (true) {
      time++;
      Pair head = dq.peekFirst();
      Pair tail = dq.peekLast();
      int nx = head.x + dx[head.dir];
      int ny = head.y + dy[head.dir];
      //base condition
      if(nx<0||ny<0||nx>N-1||ny>N-1) break; //벽 부딪
      if(map[nx][ny]==1) break; //뱀 몸에 부딪
      //run
      if (map[nx][ny] == 2) { //사과 있다면? -> 머리이동, 꼬리 그대로
        //(중요)방향 전환 있나 체크 후 기록(dir 수정)
        int dir = checkDir(time, head, qu);
        map[nx][ny] = 1;
        dq.offerFirst(new Pair(nx, ny, dir));
      } else { //사과 없다면? -> 머리이동, 꼬리 1칸 제거
        //(중요)방향 전환 있나 체크 후 추가(dir 수정)
        int dir = checkDir(time, head, qu);
        map[tail.x][tail.y] = 0;
        dq.pollLast();
        map[nx][ny] = 1;
        dq.offerFirst(new Pair(nx, ny, dir));
      }
      printAll(time); //debug
    }
    result = time;
  }

  private static void printAll(int time) {
    System.out.println(time);
    for (int i = 0; i < N; i++) {
      System.out.println(Arrays.toString(map[i]));
    }
    System.out.println();
  }

  private static int checkDir(int time, Pair head, Queue<Info> qu) {
    Info info = qu.peek();
    int dir = head.dir;
    if (info.x == time) {
      if(info.c=='D') dir = (dir+1)%4;
      if (info.c == 'L') {
        if(dir-1 < 0) dir = 3;
        else dir = dir-1;
      }
      qu.poll(); //큐 제거
    }
    return dir;
  }

  public static void main(String[] args) throws IOException {
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    K = Integer.parseInt(br.readLine());
    map = new int[N + 1][N + 1];
    for (int i = 0; i < K; i++) {
      StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
      int x = Integer.parseInt(stk.nextToken())-1;
      int y = Integer.parseInt(stk.nextToken())-1; //-1 이유:좌표 1,1을 0,0으로 맞추기 위함
      map[x][y] = 2; //사과:2
    }
    L = Integer.parseInt(br.readLine());
    Queue<Info> qu = new ArrayDeque<>();
    for (int i = 0; i < L; i++) {
      StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
      qu.offer(new Info(Integer.parseInt(stk.nextToken()), stk.nextToken().charAt(0)));
    }
    qu.offer(new Info(9999999, 'X')); //큐 모두 제거로 null 에러 방지 위해
    //run
    solve(qu);
    //output
    System.out.println(result);
  }
  static class Pair{
    int x; int y; int dir;

    Pair(int x, int y, int dir) {
      this.x=x; this.y=y; this.dir=dir;
    }
  }
  static class Info{
    int x; char c;

    Info(int x, char c) {
      this.x =x; this.c=c;
    }
  }
}

주관적인 생각의 풀이이므로 틀린 부분 지적은 언제나 환영합니다⚡

댓글남기기

참고