백준1261_알고스팟

 

x
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
​
class Node {
    int x;
    int y;
​
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
​
public class Main1261_알고스팟_Sungho {
​
    static int[][] map;
    static int[][] dist;
    static boolean[][] visited;
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, -0 };
    static int N, M;
​
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String size = br.readLine();
​
        StringTokenizer stringTokenizer = new StringTokenizer(size);
​
        M = Integer.parseInt(stringTokenizer.nextToken());// 가로의 길이(열의 수)
        N = Integer.parseInt(stringTokenizer.nextToken());// 세로의 길이(행의 수)
​
        map = new int[N][M];
        dist = new int[N][M];
        visited = new boolean[N][M];
​
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }
​
        bfs(0, 0);
    } // end of main
​
    private static void bfs(int x1, int y1) {
        Deque<Node> queue = new LinkedList<>(); // map에서 1인곳은 addFirst , 0인곳은 addLast 해주기 위해
        queue.addLast(new Node(x1, y1));
        visited[0][0] = true;
​
        while (!queue.isEmpty()) {
            Node now = queue.pollLast();
            int x = now.x;
            int y = now.y;
​
            for (int i = 0; i < 4; i++) {
                int next_x = x + dx[i];
                int next_y = y + dy[i];
​
                if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < M && !visited[next_x][next_y]) {
                    if (map[next_x][next_y] == 0) {
                        dist[next_x][next_y] = dist[x][y];
                        queue.addLast(new Node(next_x, next_y));
                    } else {
                        dist[next_x][next_y] = dist[x][y] + 1;
                        queue.addFirst(new Node(next_x, next_y));
                    }
                    visited[next_x][next_y] = true;
                } else
                    continue;
​
            }
        }
        System.out.println(dist[N - 1][M - 1]);
        /**
         * dist = { {0 , 1 , 2}, {1 , 2 , 3}, {2 , 3 , 3},} 이런식으로 쌓여가는 거
         */
    } // end of bfs
} // end of class