Java 3190 뱀

 

 

 

풀이 :

핵심 로직은 아래와 같다.

 

1. 시작점부터 큐에 넣어서 bfs로 탐색

2. HashMap에 integer, String으로 카운트 정보와 방향 정보를 저장

3. 뱀이 현재 맵에 위치한 정보들을 LinkedList에 넣고 위치한 좌표들은 bool값을 true 변경

4. 인덱스 범위가 유효하지 않거나, bool값이 true인 경우에는 뱀이 위치한 곳이기 때문에 탐색 종료

 

구현은 생각보다 빨리 끝냈지만 방향회전 하는 곳을 이상하게 해놓아서 한참을 헤매었다

 

 

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

public class Main {
    static int n, k, l;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static HashMap<Integer, String> hash = new HashMap<>();

    static int bfs(int x, int y, int direction) {
        Queue<int[]> q = new LinkedList<>(); // 탐색 큐
        q.offer(new int[]{x, y});
        visited[x][y] = true;

        LinkedList<int[]> snake = new LinkedList<>(); // 뱀의 위치를 기록하는 LinkedList
        snake.offer(new int[]{x, y});

        int currentDirection = direction; // 현재 방향
        int time = 0;

        while (!q.isEmpty()) {
            time++;

            int[] poll = q.poll();

            int cx = poll[0];
            int cy = poll[1];

            int nx = cx + dx[currentDirection];
            int ny = cy + dy[currentDirection];

            if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) {
                break;
            }

            visited[nx][ny] = true;
            q.offer(new int[]{nx, ny});

            if (map[nx][ny] == 1) {
                map[nx][ny] = 0;
            } else {
                int[] tail = snake.pollLast(); // 꼬리 제거
                visited[tail[0]][tail[1]] = false;
            }

            snake.offerFirst(new int[]{nx, ny}); // 머리 추가

            if (hash.containsKey(time)) {
                if (hash.get(time).equals("D")) {
                    currentDirection += 1;
                    if (currentDirection == 4)
                        currentDirection = 0;
                } else {
                    currentDirection -= 1;
                    if (currentDirection == -1)
                        currentDirection = 3;
                }
            }
        }

        return time;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());

        map = new int[n][n];
        visited = new boolean[n][n];

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            map[a][b] = 1;
        }

        l = Integer.parseInt(br.readLine());

        for (int i = 0; i < l; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            String b = st.nextToken();
            hash.put(a, b);
        }

        // 초기 방향 값 - 오른쪽
        int direction = 0;
        int bfs = bfs(0, 0, 0);

        System.out.println(bfs);
    }
}