[백준] 2178- 미로탐색(with.Java)

💡문제 분석 요약

-- 문제 --

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력 : 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력 : 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

💡알고리즘 설계

1. bfs - 큐

2. Scanner 의 next로 빠르게 입력받기

💡코드

package backjoon;

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

public class BackJoon2178 {
    static int N,M;
    static int[][] map;
    static boolean[][] visited;
    static int cnt=1;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][M];
        visited = new boolean[N][M];
        String str;//next로 연속으로 받으니까
        for (int i = 0; i < N; i++) {
            str = sc.next();//엔터치면 i++
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        bfs();
        System.out.println(map[N - 1][M - 1]);
    }

    public static void bfs() {
        var queue = new LinkedList<int[]>();
        queue.add(new int[]{0, 0});
        int[] tmp = new int[2];//현재위치입력
        visited[0][0]=true;
        int y, x;
        int ny,nx;
        while (!queue.isEmpty()) {
            tmp = queue.poll();
            y = tmp[0];
            x = tmp[1];
            for (int i = 0; i < 4; i++) {
                ny = y + dy[i];
                nx = x + dx[i];
                if (ny < 0 || nx < 0 || ny > N || nx > M) {
                    continue;
                }
                if (!visited[ny][nx] && map[ny][nx] == 1) {
                    visited[ny][nx]=true;
                    map[ny][nx] += map[y][x];
                    queue.add(new int[]{ny, nx});
                }
            }
        }
    }
}

💡시간복잡도

O(N*N)

💡틀린 이유

💡틀린 부분 수정 or 다른 풀이

💡느낀점 or 기억 할 정보

주석 참고