BFS유형 시 중복체크가 가장 중요하다.
그중에서도 3차원 배열로 visit배열을 선언하는 경우이다.

---

벽 부수고 이동하기(2206번)

1. 문제

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

2. 풀이

참고 풀이
https://wtg-study.tistory.com/86
https://kscodebase.tistory.com/66

2-1. ✨핵심 Point

• visit[x][y][0] : 벽을 부수지 않고 좌표(x, y)를 방문
• visit[x][y][1] : 벽을 부수고 좌표(x, y)를 방문

3. 코드

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        int moveX[] = {1, -1, 0, 0};
        int moveY[] = {0, 0, 1, -1};
        
        String map[][] = new String[N][M];
        boolean visit[][][] = new boolean[N][M][2];
        for(int i = 0; i < N; i++){
            map[i] = br.readLine().split("");
        }
        
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0, 1, false));
        visit[0][0][0] = true;
        
        while(!q.isEmpty()){
            Node node = q.poll();
            int x = node.x;
            int y = node.y;
            int count = node.count;
            boolean destroy = node.destroy;
            
            if(x == N - 1 && y == M - 1){
                System.out.println(count);
                return;
            }
            
            for(int i = 0; i < moveX.length; i++){
                int goX = x + moveX[i];
                int goY = y + moveY[i];
                
                if(goX < 0 || goY < 0 || goX >= N || goY >= M)
                    continue;
                
                if("0".equals(map[goX][goY])){ // 벽 아니면
                    
                    // 1. 부신적 X, 갈려는 노드(goX, goY)가 부수지 않고 방문이 안되었으면
                    if(!destroy && !visit[goX][goY][0]){
                        q.add(new Node(goX, goY, count+1, false));
                        visit[goX][goY][0] = true;
                    
                    // 2. 부신적 O, 갈려는 노드(goX, goY)가 부수고 방문이 안되어있다면
                    } else if(destroy && !visit[goX][goY][1]) {
                        q.add(new Node(goX, goY, count+1, true));
                        visit[goX][goY][1] = true;
                    }
                } else { // 벽이라면
                    if(!destroy){ // 부셔진지 파악하고 부수기
                        q.add(new Node(goX, goY, count+1, true));
                        visit[goX][goY][1] = true; // 부수고 난 후 방문 처리
                    }
                }
            }
        }
        System.out.println(-1); // 불가능할 때는 -1을 출력한다.
    }
    
    public static class Node {
        int x;
        int y;
        int count;
        boolean destroy;
        
        public Node(int x, int y, int count, boolean destroy){
            this.x = x;
            this.y = y;
            this.count = count;
            this.destroy = destroy;
        }
    }
}

---

2. 말이 되고픈 원숭이

1. 문제

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

2. 풀이

참고 풀이
https://yabmoons.tistory.com/48
https://moonsbeen.tistory.com/181

2-1. ✨핵심 Point

• 나이트 이동 배열 잘 확인하기!!

static int moveKx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
static int moveKy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

• K를 얼만큼 써서 이동했는지 체크해야한다.

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

3. 코드

import java.util.*;
import java.io.*;

public class Main{
    static int moveKx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
	static int moveKy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
	static int moveX[] = {0, 0, 1, -1}; // 동서남북
	static int moveY[] = {1, -1, 0, 0}; // 동서남북
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int W = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());
        
        int map[][] = new int[H][W];
        boolean visit[][][] = new boolean[H][W][31];
        for(int i = 0; i < H; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < W; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0, 0, K));
        visit[0][0][0] = true;
        
        while(!q.isEmpty()){
            Node node = q.poll();
            int x = node.x;
            int y = node.y;
            int count = node.count;
            int horse = node.horse;
            
            if(x == H - 1 && y == W - 1){
                System.out.println(count);
                return;
            }
            
            for(int i = 0; i < moveX.length; i++){
                int goX = x + moveX[i];
                int goY = y + moveY[i];

                if(goX < 0 || goY < 0 || goX >= H || goY >= W)
                    continue;

                if(map[goX][goY] == 1 || visit[goX][goY][horse])
                    continue;

                q.add(new Node(goX, goY, count+1, horse));
                visit[goX][goY][horse] = true;
            }  
            
            if(horse > 0){
                for(int i = 0; i < moveKx.length; i++){
                    int goX = x + moveKx[i];
                    int goY = y + moveKy[i];
                    
                    if(goX < 0 || goY < 0 || goX >= H || goY >= W)
                        continue;
                    
                    if(map[goX][goY] == 1 || visit[goX][goY][horse-1])
                        continue;
                    
                    q.add(new Node(goX, goY, count+1, horse-1));
                    visit[goX][goY][horse-1] = true;
                }
            } 
        }
        System.out.println(-1);
    }
    
    public static class Node {
        int x;
        int y;
        int count;
        int horse;
        
        public Node(int x, int y, int count, int horse){
            this.x = x;
            this.y = y;
            this.count = count;
            this.horse = horse;
        }
    }
}