[java 백준]실버 1/2178번 미로찾기

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class Dot {
    int x;
    int y;
 
    public Dot(int x, int y) {
        this.x = x;
        this.y = y;
    }
 
}
 
public class Main {
 
    public static int m;
    public static int n;
    public static int[][] arr;
    public static boolean[][] visited;
    public static int[] dirX = { -1, 1, 0, 0 };
    public static int[] dirY = { 0, 0, -1, 1 };
 
    public static Queue<Dot> queue;
 
    public static void bfs(int i, int j) {
        queue.add(new Dot(i, j));
        while (!queue.isEmpty()) {
            Dot dot = queue.poll();
            int x = dot.x;
            int y = dot.y;
 
            for (int i1 = 0; i1 < 4; i1++) {
                int X = dot.x + dirX[i1];
                int Y = dot.y + dirY[i1];
                if (X >= 0 && X < n && Y >= 0 && Y < m) {
 
                    if (visited[X][Y] == false && arr[X][Y] == 1) {
 
                        queue.add(new Dot(X, Y));
                        visited[X][Y] = true;
                        arr[X][Y] = arr[x][y] + 1;
 
                        
 
                    }
                }
            }
 
        }
 
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n][m];
        visited = new boolean[n][m];
        queue = new LinkedList<Dot>();
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            for (int j = 0; j < m; j++) {
                arr[i][j] = s.charAt(j) - '0';
                visited[i][j] = false;
 
            }
        }
 
        visited[0][0] = true;
        bfs(0, 0);
        System.out.println(arr[n - 1][m - 1]);
 
    }
}

 

7576번 토마토와 비슷한 문제인데 방문했는지 bool형의 visited 2차원 배열을 만들어주는것이 핵심이다!

https://we1cometomeanings.tistory.com/167

[java 백준] 실버 1/7576번 토마토

 

풀면서 아쉬웠던 점

 

나는 이동경로의 횟수를 ans라는 변수에 담아주고, BFS로 탐색할때 마다 ans를 1씩 더해준 후(큐에 현재 인덱스가 담길 때)   인덱스가 n,m이 될때 ans를 return 해주는 방식을 취했는데 이러니까 답이 틀리게 나왔다.

더 좋은 방식은 arr[x][y]=arr[node.x][node.y]+1을 해주는 것이였다. 이동한 위치=이전 위치 +1을 해주면 더 정확히 구할 수 있었고, 어차피 첫번째 인덱스인 arr[1][1]의 값이 1이기 때문에 새로운 배열을 만들필요도 없었다. 

 

 

<읽어보면 좋은글>

https://sarah950716.tistory.com/m/12

[그래프] 인접 행렬과 인접 리스트