[BOJ - JAVA] 3190 - 뱀 (큐, BFS, 시뮬레이션)

# 주소

https://www.acmicpc.net/problem/3190

3190번: 뱀

# 문제

 

# 문제 해설 및 코드리뷰

package com.board.dream;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    static int n,m,t;
    static int[][] arr;
    static boolean [][] visit;
    static int dx[] = {-1,0,1,0};
    static int dy[] = {0,1,0,-1};
    static HashMap<Integer, Character> map;
    static int length = 0;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n+1][n+1];
        visit = new boolean[n+1][n+1];
        while (m-- > 0) {
            int x = scan.nextInt();
            int y = scan.nextInt();
            arr[x][y] = 1;
        }
        t = scan.nextInt();
        map = new HashMap<>();
        while (t-- > 0) {
            int x = scan.nextInt();
            char str = scan.next().charAt(0);
            map.put(x,str);
        }
        bfs(1,1);
        System.out.println(length+1);
    }
    public static void bfs(int x, int y) {
        Queue<Node> queue = new LinkedList<>();
        Queue<Node> snake = new LinkedList<>();
		visit[x][y] = true;
        queue.offer(new Node(x, y, 0));
        snake.offer(new Node(x, y));
        int dir = 1;
        int snailX = x;
        int snailY = y;
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            int nx = now.x;
            int ny = now.y;
            int ntime = now.time;
            if (map.containsKey(ntime)) {
                char key = map.get(ntime);
                if (key == 'D') {
                    dir = setRight(dir);
                } else
                    dir = setLeft(dir);
                map.remove(ntime);
            }
            int qx = nx + dx[dir];
            int qy = ny + dy[dir];
            if (qx < 1 || qy < 1 || qx > n || qy > n) {
                length = ntime;
                break;
            }
            if (visit[qx][qy]) {
                length = ntime;
                break;
            }
            if (arr[qx][qy] == 0) {
                visit[snailX][snailY] = false;
                snake.poll();
                snake.offer(new Node(qx, qy));
                snailX = snake.peek().x;
                snailY = snake.peek().y;
            } else {
                arr[qx][qy] = 0;
                snake.offer(new Node(qx, qy));
            }
            visit[qx][qy] = true;
            queue.offer(new Node(qx, qy, ntime + 1));
        }
    }
    public static int setLeft ( int dir){
        switch (dir) {
            case 0:
                return 3;
            case 1:
                return 0;
            case 2:
                return 1;
            case 3:
                return 2;
        }
        return 0;
    }
    public static int setRight(int dir){
        switch(dir){
            case 0:
                return 1;
            case 1:
                return 2;
            case 2:
                return 3;
            case 3:
                return 0;
        }
        return 0;
    }
}
class Node{
    int x;
    int y;
    int time;
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
    Node(int x, int y, int time) {
        this.x = x;
        this.y = y;
        this.time = time;
    }
}

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
arr = new int[n+1][n+1];
visit = new boolean[n+1][n+1];
while (m-- > 0) {
    int x = scan.nextInt();
    int y = scan.nextInt();
    arr[x][y] = 1;
}

Scanner 를 이용하여 n과 m을 입력받은 뒤 arr를 n+1크기로 2차원 선언합니다.

visit또한 마찬가지입니다. 

여기서 인덱스가 0인 행, 열 지점은 사용하지 않을 것이므로 입력되는 x와 y를 그대로 arr[x][y]에 1로 넣습니다.

 

t = scan.nextInt();
map = new HashMap<>();
while (t-- > 0) {
    int x = scan.nextInt();
    char str = scan.next().charAt(0);
    map.put(x,str);
}

그리고 t를 입력받는데, 이 t는 위치 변환의 횟수입니다.

예제에서 3이 입력되므로 t는 3이될 것이고 이 입력받는 값이 첫 번째는 정수, 두 번째는 문자이기 때문에 어떻게 입력받는것이 좋을지 첨엔 고민했었습니다.

그래서 Queue를 이용해서 풀어서 class로 만들어 풀려고 했는데 계속 queue를 사용해야해서 방향을 좀 틀었습니다.

뒤에 계속 queue가 나오니까 제가 뭘 썼던지 헷갈리더라구요 ㅠㅠㅠ..

그래서 전 HashMap을 이용했습니다.

이 hashmap에 앞의 인자는 int, 뒤의 인자는 char형태로 데이터를 삽입합니다.

그리고 bfs에 1,1을 넣고 실행합니다.

Queue<Node> queue = new LinkedList<>();
Queue<Node> snake = new LinkedList<>();
visit[x][y] = true;
queue.offer(new Node(x, y, 0));
snake.offer(new Node(x, y));

제가 이렇게 사용하려고 queue를 앞에서 선언 안했습니다.

class Node{
    int x;
    int y;
    int time;
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
    Node(int x, int y, int time) {
        this.x = x;
        this.y = y;
        this.time = time;
    }
}

그래서 Node class를 오버로드하여 인자가 2개인 것, 3개인 것을 따로 선언했습니다.

(class를 개별로 만들어도 됩니다.)

queue의 Queue는 time을 갖고다니는 큐입니다. 이 queue는 실제 좌표 인덱스를 움직이면서 값을 탐색할 때 담을 queue입니다.

snake의 Queue는 움직이는 뱀의 위치를 나타냅니다.

그리고

int dir = 1;
int snailX = x;
int snailY = y;

dir = 1이라 선언할 것입니다.

이 때 dir = 1이나 다른 숫자도 됩니다 어짜피 다른 이상한 방향으로 가면 걸러지기 때문에요.

snailX와 snailY는 x와 y로 각각 받아옵니다.

이것이 현재 있는 뱀의 위치 값입니다. 처음엔 1,1이겠죠?

while (!queue.isEmpty()) {
    Node now = queue.poll();
    int nx = now.x;
    int ny = now.y;
    int ntime = now.time;
    if (map.containsKey(ntime)) {
        char key = map.get(ntime);
        if (key == 'D') {
            dir = setRight(dir);
        } else
            dir = setLeft(dir);
        map.remove(ntime);
    }

Node의 now = queue.poll()로 갖고와서 now에 담습니다.

그리고 nx와 ny 는 현재 now의 x,y점이고 ntime에 현재의 시간이라고 합시다.

그리고 만약 map에 ntime의 시간을 갖고 있으면 (예제에서는 3초에 D였으므로)

key에 map에서 ntime때의 key값을 가져온 뒤 key가 D 또는 L인지에 따라 방향을 다르게 설정합니다.

그리고 방향을 바꾸고 map에서 ntime을 제거합니다.

int qx = nx + dx[dir];
int qy = ny + dy[dir];
if (qx < 1 || qy < 1 || qx > n || qy > n) {
    length = ntime;
    break;
}
if (visit[qx][qy]) {
    length = ntime;
    break;
}

이후 qx와 qy의 좌표를 새로 설정할 것인데요.

갖고온 dir방향에 따라 qx와 qy는 새로 마련될 것입니다.

그런데 이 qx와 qy가 벽에 부딪히게되면 (인덱스가 0인 지점) length에는 ntime을 담고 break시킵니다.

마찬가지로 visit은 여기서 방문 노드라기보단 자신의 몸통 노드라고 이해해볼텐데요.

만약 qx와 qy가 몸통 노드라면 이 때에도 break시키면 되겠습니다.

자 이후부터가 이제 문제의 핵심인데요.

 if (arr[qx][qy] == 0) {
        visit[snailX][snailY] = false;
        snake.poll();
        snake.offer(new Node(qx, qy));
        snailX = snake.peek().x;
        snailY = snake.peek().y;
    } else {
        arr[qx][qy] = 0;
        snake.offer(new Node(qx, qy));
    }
    visit[qx][qy] = true;
    queue.offer(new Node(qx, qy, ntime + 1));
}

arr가 0인지 아닌지, 그러니까 사과가 놓여있는지 아닌지에 따라 당연히 푸는 방식이 바뀝니다.

만약 사과가 없는 곳이라면(arr가 0이라면) visit을 이용하여 snailX와 snailY를 false로 바꿉니다.

이 snailX와 snailY는 원래 뱀이 있던 지점인데, 새로운 위치에 사과가 없으므로 뱀은 크기를 늘리지 않고 새로 이동합니다.

따라서 visit은 false로 바꾸어 주고 snake의 처음 점을 poll()을 써서 제거합니다.

그리고 snail에는 새로운 점을 삽입합니다(qx,qy)

이후 snailX와 snailY는 새로운 x와 y를 가지게 됩니다.

그런데 arr가 1이라면 (사과가 있다면) arr[qx][qy] = 0로 바꾼 뒤 snake에는 새로운 점을 삽입합니다. 이게 다입니다.

다 끝나고 난뒤 visit을 true로 변경하고 queue에도 새로운 점을 삽입하고 ntime에 +1하여 시간을 늘립니다.

public static int setLeft ( int dir){
    switch (dir) {
        case 0:
            return 3;
        case 1:
            return 0;
        case 2:
            return 1;
        case 3:
            return 2;
    }
    return 0;
}
public static int setRight(int dir){
    switch(dir){
        case 0:
            return 1;
        case 1:
            return 2;
        case 2:
            return 3;
        case 3:
            return 0;
    }
    return 0;
}

이건 참고해주세요. setLeft와 setRight에 따라 이동하는 방향을 이렇게 설정할 수 있습니다.

자료구조에서 queue가 3개가 되어 혼란이 많았지만 hashmap으로 하니까 그나마 간단했습니다.

감사합니다.