📝문제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 미로의 최단거리(BFS) //
public class Main {
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    // 2차원 미로 배열
    static int[][] board;
    // 방문 유무를 저장할 배열
    static boolean[][] check;
    // 방문 거리를 저장
    static int[][] dist;
    
    static void bfs(int x,int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {x,y});
        check[x][y] = true;
        while (!queue.isEmpty()) {
            int[] now = queue.poll(); // (1,1) -> 출발지점 (포함x)
            for(int i=0; i<4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if(nx>=1 && nx<=7 && ny>=1 && ny<=7) {
                    if(board[nx][ny] !=1 && !check[nx][ny]) {
                        check[nx][ny] = true;
                        dist[nx][ny] = dist[now[0]][now[1]] + 1;
                        queue.add(new int[] {nx,ny});
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        board = new int[8][8];
        check = new boolean[8][8];
        dist = new int[8][8];
        for(int i=1; i<8; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for(int j=1; j<8; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        board[1][1] = 1;
        check[1][1] = true;
        bfs(1,1);
        if(dist[7][7] == 0 ) {
            System.out.println("-1");
        } else {
            System.out.println(dist[7][7]);
        }
    }
}

<입력>
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0

<출력>
12

⭐️ 변수 설명

• 2차원 미로 변수 7x7
  static int[][] board;
• 방문 유(true)무(false)만을 저장할 변수 7x7
  static boolean[][] check;
• 방문한 최단거리를 저장할 변수 7x7
  static int[][] dist;
  

✅ 내가 헤맸던 부분 ?

처음에 문제에 접근했을 땐, 다음과 같이 board 배열을 지나가면서 0이면 +1 씩 저장하면서 검사를 하려했었지만,,

😅수정 전

 if(nx>=1 && nx<=7 && ny>=1 && ny<=7) {
                    if(board[nx][ny] !=1 && !check[nx][ny]) {
                        check[nx][ny] = true;
                        board[nx][ny] = board[now[0]][now[1]] + 1;
                        queue.add(new int[]{x,y});
                    }
                }

답이 안나오길래 생각을 해보니 board[1][1] =1; 을 해놓기만 했으니 다른 배열들은 다 0이여서 그랬다..(흐으ㅇㅡㄱ..)

그래서 들렸다고!!! 확인만 체크해줄 check 배열을 만들었고, 같은 크기의 거리를 저장 시켜줄 배열(dist)을 만들었다.

😉수정 후

if(nx>=1 && nx<=7 && ny>=1 && ny<=7) {
                    if(board[nx][ny] !=1 && !check[nx][ny]) {
                        check[nx][ny] = true;
                        dist[nx][ny] = dist[now[0]][now[1]] + 1;
                        queue.add(new int[] {nx,ny});
                    }
                }

.
.

이렇게 되면 dist 배열에 +1 씩 저장해 나가면서 안들렸던 곳들을 방문하고 마지막(7,7) 까지 거리가 저장이 되고 , 출력하면 끝!

📝 풀어보면 좋을 문제 - 백준 2178번 - 미로탐색

.
.
.

✅ 추가 1

static int[] dx = {-1,0,1,0};
static int[] dy = {0,1,0,-1};

(dx,dy) 라고 생각했을 때,

(-1,0) -> 12시 방향
(0,1) -> 3시 방향
(1,0) -> 6시 방향
(0,-1) -> 9시 방향

✅ 추가 2

queue.offer(new int[] {x,y});

• int[] 배열:
  Java에서는 배열을 사용하여 여러 개의 동일한 타입의 데이터를 하나의 변수에 저장할 수 있습니다.
• new int[] {x, y}는 크기가 2인 정수 배열을 생성하고, 그 배열에 x 와 y 값을 순서대로 저장합니다.
  queue.offer(new int[] {x, y});:
• 이 문장은 x 와 y 값을 가진 새로운 배열을 생성하고 그 배열을 queue에 추가, 이렇게 함으로써, queue에는 {x, y} 형태의 배열이 저장됩니다. 이 배열은 미로 탐색 등의 알고리즘에서 2차원 공간의 좌표를 나타내는 데 사용되는 일반적인 방법