링크텍스트

미로탐색 문제

1이 부여된 곳에만 이동이 가능하다는 점과 최단거리를 탐색한다는 점에서 BFS 탐색을 통해 해당 배열에 도달할 수 있는 숫자를 저장하여 마지막 도착점에 최단거리로 탐색할 수 있는 숫자를 저장하였다.

인접한 곳중 상하좌우로만 이동 가능하다는 점에서

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

이 부분을 사용하였다.

대략적인 설계
0,0 을 시작으로 BFS 호출해서 해당 점 y,x 또는 i행 j열 를 가지고 큐에 넣고 큐가 안비어있을 떄까지 루프를 돌고 해당 y,x에 dx|dy의 길이만큼 돌면서 배열의 범위를 벗어나는 부분을 체크하고 해당 지점이 '1'로 이동할 수 있는지 판단하고 해당 갈 지점에 현재 위치한 y,x의 값에 +1을 해주는 발자취를 남긴다.

package oneDay_twoSol.DB_FirstSearch;


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

public class mazeSearch {
    static int dy[] = {-1, 1, 0, 0};
    static int dx[] = {0, 0, -1, 1};
    // 위 아래 왼쪽 위
    static boolean visited[][]; // 방문 배열.
    static int matrix[][]; //  adjecent Matrix
    static int distance[][]; //각 위치의 최단거리 저장 배열.
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        matrix = new int[n][m];
        visited = new boolean[n][m];
        distance =new int[n][m];
        sc.nextLine();
        for (int i = 0; i < n; i++) {
            String str[] = sc.nextLine().split("");
            for (int j = 0; j < m; j++) {
                matrix[i][j] = Integer.parseInt(str[j]);
            }
        }

        bfs(0, 0);
       /* for (int i = 0; i <distanc.length ; i++) {
            for (int j = 0; j <distanc[i].length ; j++) {
                System.out.print(distanc[i][j]+" ");
            }
            System.out.println();
        }*/
    }




    static void bfs(int y, int x) {
        visited[y][x]=true;
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(y, x));
        while (!q.isEmpty()) {
            Node node = q.poll();
            y = node.getY();
            x = node.getX();
            for (int i = 0; i < 4; i++) {
                int tmpY = y + dy[i];
                int tmpX = x + dx[i];
                if (tmpX >= 0 && tmpX < m && tmpY < n && tmpY >= 0) {
                    if (matrix[tmpY][tmpX] == 1&&!visited[tmpY][tmpX] && distance[tmpY][tmpX]==0) {
                        visited[tmpY][tmpX]=true;
                        distance[tmpY][tmpX] = distance[y][x] + 1;
                        q.offer(new Node(tmpY, tmpX));
                    }
                }
            }
        }
        System.out.println(distance[n - 1][m - 1]+1);
    }

    static class Node {
        private int y;
        private int x;

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

        public int getY() {
            return y;
        }

        public int getX() {
            return x;
        }
    }
}