백준 미로 만들기

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

2665번: 미로만들기

 

다이크스트라를 이해하고 잇어야 쉽게 풀었겟네요.

 

한 5일정도 풀다가 더이상 안풀려서 대학때 배운 다이크스트라 다시 보니 좀 이해가 되네요 ㅠ 

으휴 ㅠ 다음에 비슷한문제로 좀 풀어봐야겟네요 ㅠ 

import java.util.*;

public class Main {
    private int x;
    private int y;

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

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

    public int getY() {
        return this.y;
    }

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

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        int[][] maps = new int[n][n];
        int[][] dist = new int[n][n];

        for (int i = 0; i < n; i++) {
            String tmp = scan.nextLine();
            for (int j = 0; j < tmp.length(); j++) {
                maps[i][j] = tmp.charAt(j) - '0';
                dist[i][j] = -1;
            }
        }

        Queue<Main> queue = new LinkedList<>();
        queue.add(new Main(0, 0));
        dist[0][0] = 0; 

        while (!queue.isEmpty()) {
            Main current = queue.poll();

            for (int i = 0; i < 4; i++) {
                int tmpDiri = current.getX() + dx[i];
                int tmpDirj = current.getY() + dy[i];

                if (tmpDiri < 0 || tmpDirj < 0 || tmpDiri >= n || tmpDirj >= n) {
                	continue; 
                } 

                int nextDist = dist[current.getX()][current.getY()];
                if (maps[tmpDiri][tmpDirj] == 0) {
                	nextDist += 1; 
                }

                if (dist[tmpDiri][tmpDirj] == -1 || dist[tmpDiri][tmpDirj] > nextDist) {
                    dist[tmpDiri][tmpDirj] = nextDist;
                    queue.add(new Main(tmpDiri, tmpDirj));
                }
            }
        }

        System.out.println(dist[n - 1][n - 1]); 
    }
}