백준 골드3 말이 되고픈 원숭이

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

문제

풀이

가중치 없는 최단 거리 = bfs
bfs로 문제를 풀어나갔다.

말의 걸음에 관한 좌표를 dx, dy로 저장했고, 원숭이에 대한 좌표를 nx, ny로 저장했다.
큐에는 x, y 좌표와 총 걸음, 말의 걸음 횟수를 저장했다.
그렇게 말의 걸음이 K가 되면 더이상 말의 걸음을 사용하지 못하게 했다.

문제 안 테스트케이스도 잘 나와서 혼자 잘 푼 줄 알았다...!

(아래 코드에서 말의 좌표(dx, dy)가 8개가 아닌 이유는 맨 왼쪽 상단부분은 목표가 오른쪽 아래방향이라 필요 없을거라 생각했었다
-> 하지만 있는 방향 다 써야 됐나봄. 이거 하나로 시간초과 나지도 않고 bfs인 이상 괜찮은 것 같다.)

하지만 "틀렸습니다"

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int K, W, H, cnt = 0, count=0;
    static int[][] arr;
    static boolean[][] visit;
    static int dx[] = { 2, 1, 2, 1, -2, -1};
    static int dy[] = { 1, 2, -1, -2, 1, 2};
    static int nx[] = { 1, -1, 0, 0};
    static int ny[] = { 0, 0, -1, 1};
    static boolean flag;


    public static void main(String[] args) throws Exception{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(bufferedReader.readLine());

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        W = Integer.parseInt(stringTokenizer.nextToken());
        H = Integer.parseInt(stringTokenizer.nextToken());

        arr = new int[H][W];
        visit = new boolean[H][W];

        for(int i=0;i<H;i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for(int j=0;j<W;j++){
                arr[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        bfs(0,0);

        if(!flag){
            System.out.println(cnt);
        } else{
            System.out.println(-1);
        }
    }

    static void bfs(int x, int y){
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(x, y, 0, 0));

        while(!queue.isEmpty()){
            Node node = queue.poll();

            if(node.horse < K) {
                for (int i = 0; i < 6; i++) {
                    int new_x = node.x + dx[i];
                    int new_y = node.y + dy[i];

                    if (check(new_x, new_y)) {
                        if (new_x == W-1 && new_y == H-1) {
                            cnt = node.c + 1;
                            return;
                        }
                        count++;
                        queue.offer(new Node(new_x, new_y, node.c + 1, node.horse + 1));
                        visit[new_y][new_x] = true;
                    }
                }
            }
            for(int i=0;i<4;i++){
                int new_x = node.x + nx[i];
                int new_y = node.y + ny[i];

                if(check(new_x, new_y)){
                    if(new_x == W-1 && new_y == H-1){
                        cnt = node.c + 1;
                        return;
                    }

                    queue.offer(new Node(new_x, new_y, node.c+1, node.horse));
                    visit[new_y][new_x] = true;
                }
            }
        }
        flag = true;
    }

    static boolean check(int x, int y){
        if(x < 0 || y < 0 || x >= W || y >= H || visit[y][x] || arr[y][x] == 1){
            return false;
        }
        return true;
    }

    static class Node{
        int x, y, c, horse;
        Node(int x, int y, int c, int horse){
            this.x=x;
            this.y=y;
            this.c=c;
            this.horse=horse;
        }
    }
}

2번째 풀이

이 문제는 visit 처리를 더 신중하게 했어야 했다.
이미 방문했어도 말의 걸음으로 방문할 수도, 원숭이의 걸음으로 방문할 수도 있기 때문이다.
이렇게 방문하는 경우에 따라 처리를 다르게 해야 할 경우 visit를 3차원 배열로 선언해야 한다.
말의 걸음일 경우에도 어떻게 시작한 말의 걸음인지? 구분하기 위해 말의 걸음일 경우
visit[x][y][node.horse+1]을 하고 원숭이는 visit[x][y][node.horse]를 하였다.

하지만 "메모리 초과"

근데 글 적으면서 헷갈리는거...
!visit[new_y][new_x][node.horse]에 대해 방문 처리 하고
visit[new_y][new_x][node.horse+1] = true;
이걸 방문 처리 하지?
-> 싶었지만 이게 문제였네 😂

for (int i = 0; i < 8; i++) {
                    int new_x = node.x + dx[i];
                    int new_y = node.y + dy[i];
                    if (check(new_x, new_y)) {
                        if (new_x == W-1 && new_y == H-1) {
                            cnt = node.c + 1;
                            return;
                        }
                        if(!visit[new_y][new_x][node.horse]) {
                            queue.offer(new Node(new_x, new_y, node.c + 1, node.horse + 1));
                            visit[new_y][new_x][node.horse+1] = true;
                        }
                    }
                }
          }
     }
 }             

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int K, W, H, cnt = 0;
    static int[][] arr;
    static boolean[][][] visit;
    static int dx[] = { 2, 1, 2, 1, -2, -1, -2, -1};
    static int dy[] = { 1, 2, -1, -2, 1, 2, -1, -2};
    static int nx[] = { 1, -1, 0, 0};
    static int ny[] = { 0, 0, -1, 1};
    static boolean flag;


    public static void main(String[] args) throws Exception{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(bufferedReader.readLine());

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        W = Integer.parseInt(stringTokenizer.nextToken());
        H = Integer.parseInt(stringTokenizer.nextToken());

        arr = new int[H][W];
        visit = new boolean[H][W][31];

        for(int i=0;i<H;i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for(int j=0;j<W;j++){
                arr[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        bfs(0,0);

        if(!flag){
            System.out.println(cnt);
        } else{
            System.out.println(-1);
        }
    }

    static void bfs(int x, int y){
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(x, y, 0, 0));
        visit[y][x][0] = true;
        
        while(!queue.isEmpty()){
            Node node = queue.poll();

            if(node.horse < K) {
                for (int i = 0; i < 8; i++) {
                    int new_x = node.x + dx[i];
                    int new_y = node.y + dy[i];

                    if (check(new_x, new_y)) {
                        if (new_x == W-1 && new_y == H-1) {
                            cnt = node.c + 1;
                            return;
                        }
                        if(!visit[new_y][new_x][node.horse]) {
                            queue.offer(new Node(new_x, new_y, node.c + 1, node.horse + 1));
                            visit[new_y][new_x][node.horse+1] = true;
                        }
                    }
                }
            }
            for(int i=0;i<4;i++){
                int new_x = node.x + nx[i];
                int new_y = node.y + ny[i];

                if(check(new_x, new_y)){
                    if(new_x == W-1 && new_y == H-1){
                        cnt = node.c + 1;
                        return;
                    }
                    if(!visit[new_y][new_x][node.horse]) {
                        queue.offer(new Node(new_x, new_y, node.c + 1, node.horse));
                        visit[new_y][new_x][node.horse] = true;
                    }
                }
            }
        }
        flag = true;
    }

    static boolean check(int x, int y){
        if(x < 0 || y < 0 || x >= W || y >= H || arr[y][x] == 1){
            return false;
        }
        return true;
    }

    static class Node{
        int x, y, c, horse;
        Node(int x, int y, int c, int horse){
            this.x=x;
            this.y=y;
            this.c=c;
            this.horse=horse;
        }
    }
}

네... 위에 적은 부분

!visit[new_y][new_x][node.horse]에 대해 방문 처리 하고
visit[new_y][new_x][node.horse+1] = true;

이게 문제 였어요.
왜냐면 새로운 좌표에 대한 visit를 판단하는거니까 새로운 node.horse도 했어야죠 ㅠ

그래도 메모리 초과가 자료구조 많이 써서 나오는건 줄만 알았는데 럭키비키예요 ;)
자료구조 뭐 지워야 하는건가? 싶었거든요

이거 해결하니까 성공했을까요?

96%쯤인가 "틀렸습니다."
(진짜 맞을 줄 알고 끝났다 하고 일어났었는데 ㅠ-ㅠ)

3번째 풀이

문제를 잘 보면 좌표가 1,1일수도 있어요.
하지만 1,1은 갈 수 있는 좌표가 없어서 무사히 while문을 빠져나와 flag가 true가 됐죠.
그래서 예외로 1,1일 경우, 즉 출발지와 목적지가 같을 경우 0으로 처리되게 해주었어요.

그렇게 성공!!!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int K, W, H, cnt = 0;
    static int[][] arr;
    static boolean[][][] visit;
    static int dx[] = { 2, 1, 2, 1, -2, -1, -2, -1};
    static int dy[] = { 1, 2, -1, -2, 1, 2, -1, -2};
    static int nx[] = { 1, -1, 0, 0};
    static int ny[] = { 0, 0, -1, 1};
    static boolean flag;


    public static void main(String[] args) throws Exception{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(bufferedReader.readLine());

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        W = Integer.parseInt(stringTokenizer.nextToken());
        H = Integer.parseInt(stringTokenizer.nextToken());

        arr = new int[H][W];
        visit = new boolean[H][W][31];

        for(int i=0;i<H;i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for(int j=0;j<W;j++){
                arr[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        if(H==1 && W==1) {
            cnt = 0;
        } else {
            bfs(0, 0);
        }
        
        if(!flag){
            System.out.println(cnt);
        } else{
            System.out.println(-1);
        }
    }

    static void bfs(int x, int y){
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(x, y, 0, 0));
        visit[y][x][0] = true;

        while(!queue.isEmpty()){
            Node node = queue.poll();

            if(node.horse < K) {
                for (int i = 0; i < 8; i++) {
                    int new_x = node.x + dx[i];
                    int new_y = node.y + dy[i];

                    if (check(new_x, new_y)) {
                        if (new_x == W-1 && new_y == H-1) {
                            cnt = node.c + 1;
                            return;
                        }
                        if(!visit[new_y][new_x][node.horse + 1]) {
                            queue.offer(new Node(new_x, new_y, node.c + 1, node.horse + 1));
                            visit[new_y][new_x][node.horse + 1] = true;
                        }
                    }
                }
            }
            for(int i=0;i<4;i++){
                int new_x = node.x + nx[i];
                int new_y = node.y + ny[i];

                if(check(new_x, new_y)){
                    if(new_x == W-1 && new_y == H-1){
                        cnt = node.c + 1;
                        return;
                    }
                    if(!visit[new_y][new_x][node.horse]) {
                        queue.offer(new Node(new_x, new_y, node.c + 1, node.horse));
                        visit[new_y][new_x][node.horse] = true;
                    }
                }
            }
        }
        flag = true;
    }

    static boolean check(int x, int y){
        if(x < 0 || y < 0 || x >= W || y >= H || arr[y][x] == 1){
            return false;
        }
        return true;
    }

    static class Node{
        int x, y, c, horse;
        Node(int x, int y, int c, int horse){
            this.x=x;
            this.y=y;
            this.c=c;
            this.horse=horse;
        }
    }
}

---

요약

• 방문 처리할 때 경우에 따라 방문 처리를 다르게 해주어야 할 경우 3차원 visit 배열 쓰기
• 문제 잘 읽기. 예외가 있을지 확인하기 (ex. (1,1) 좌표 등)