[백준/JAVA] 3190번: 뱀

🔺 문제

3190번: 뱀

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0, 1, 0, -1};   // 동 남 서 북
    static int[] dy = {1, 0, -1, 0};
    
    static int N, apple, L;
    static int[][] board;
    static List<int[]> snake = new ArrayList<>(); // 🔔
    static HashMap<Integer, String> map = new HashMap<>(); // 🔔
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());     // 보드 크기
        apple = Integer.parseInt(br.readLine()); // 사과 개수
        
        board = new int[N][N];
        while(apple --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            
            board[a][b] = 1;    // 사과 위치
        }
        
        L = Integer.parseInt(br.readLine());    // 뱀의 방향 변환 횟수
        while(L --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int X = Integer.parseInt(st.nextToken());
            String cmd = st.nextToken();
            
            map.put(X, cmd);
        }
        
       solve();
    }
    
    private static void solve() {
        // 시작점
        int x = 0;
        int y = 0;
        
        int time = 0;
        int d = 0;
        snake.add(new int[] {0, 0});
        
        while(true) {
            // 1. 시간 재기
            time++;
            
            // 2. 뱀 이동하기
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            // 3. 범위를 벗어나거나, 뱀 몸통 만나면 종료
            if(isFinish(nx,ny)) {
                break;
            }
                
            // 4. 사과 있는지 체크
            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); // snake 꼬리 제거
            }
            
            // 5. 방향 바꿔주는 시간일 때, 방향 변경
            if(map.containsKey(time)) {
                if(map.get(time).equals("D")) { // 오른쪽으로 90도 회전
                    d += 1;
                    if(d == 4) d = 0;
                }
                else {  // 왼쪽으로 90도 회전
                    d -= 1;
                    if(d == -1) d = 3;      
                }
            }
            
            // 6. 현재 이동 좌표 업데이트
            x = nx;
            y = ny;
        }
        
        System.out.println(time);
    }
    
    private static boolean isFinish(int nx, int ny) {
        if(nx < 0 || ny < 0 || nx >= N || ny >= N) {
            return true;
        }
        
        for(int i = 0 ; i < snake.size() ; i++) {
            int[] tmp = snake.get(i);
            
            if(nx == tmp[0] && ny == tmp[1]) {
                return true;
            }
        }
        return false;
    }
}

✅ 해결 아이디어
✔ 구현 - 큐
while(true) {
  1. 시간재기
  2. 뱀 이동하기
  3. 범위를 벗어나거나, 뱀 몸통 만날 때 종료
  4. 사과가 있을 때 없을 때 처리
  5. 방향 바꿔주는 시간 만날 때 방향 변경
  6. 현재값 업데이트
}

 

 

---

🔺 다른 풀이들

- 거의 비슷한데 큐 사용하심 

https://loosie.tistory.com/269

[BOJ] 백준 3190번 뱀 (Java)

 

---

💬 느낀 점

이런 뱀 같은 문제를 봤나...........ㅎ

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[백준] 3190번 뱀 - Java, 자바

 

[Java] 백준 3190번 뱀

 

 

- dx, dy 관련 & 뱀의 다음 방향 설정 부분도 약간 다르심

[백준] 3190번 뱀 (Java)

 

 

- 그림 과정

백준 3190번 : 뱀 java