12日目

プログラマ

質問：ゲームマップ最短距離

に答える

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

class Solution {
    
    // 상하좌우
    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};

    private static int m;
    private static int n;

    private static boolean[][] visited;
    
    public static int solution(int[][] maps) {
        m = maps.length;
        n = maps[0].length;
        visited = new boolean[m][n];
        visited[0][0] = true;
        return bfs(0, 0, maps);
    }

    private static int bfs(int x, int y, int[][] maps) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(x, y, 1));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.getX() == maps.length - 1 && node.getY() == maps[0].length) {
                return node.getCount();
            }

            for (int i = 0; i < 4; i++) {
                int nx = node.getX() + dx[i];
                int ny = node.getY() + dy[i];

                if (nx == m - 1 && ny == n - 1) {
                    return node.getCount() + 1;
                }

                if (nx >= 0 && ny >= 0 && nx < m && ny < n && maps[nx][ny]==1 && !visited[nx][ny]) {
                    queue.add(new Node(nx, ny, node.getCount() + 1));
                    visited[nx][ny] = true;
                }
            }
        }
        return -1;
    }

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

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public int getCount() {
            return count;
        }
    }
}