[백준 / java] 2178 : 미로 탐색

chaen-ing·2024년 4월 16일
0

1일1백준

목록 보기
17/18

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

package boj2178;

import java.io.*;
import java.util.*;

public class Main {
    static int [][] maze;
    static int [][] dist;
    static boolean [][] visited;
    static int [] DX = {1,-1,0,0};
    static int [] DY = {0,0,1,-1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        maze = new int[N][M];
        dist = new int[N][M];
        visited = new boolean[N][M];

        // 미로 입력 받기
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                maze[i][j] = str.charAt(j) - '0';
                dist[i][j] = Integer.MAX_VALUE;
            }
        }

        Queue <Node> queue = new LinkedList<>();

        // 시작 노드
        queue.offer(new Node(0,0));
        visited[0][0] = true;
        dist[0][0] = 1;

        while(!queue.isEmpty()){
            Node node = queue.poll();

            for(int k = 0; k < 4; k++){
                int dx = node.x + DX[k];
                int dy = node.y + DY[k];

                if(dx < 0 || dx >= N || dy < 0 || dy >= M){
                    continue;
                }
                else if(maze[dx][dy] == 1 && !visited[dx][dy]){
                    queue.offer(new Node(dx,dy));
                    visited[dx][dy] = true;
                    dist[dx][dy] = dist[node.x][node.y] + 1;
                }
            }
        }

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

class Node{
    int x, y;

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

}

profile
💻 개발 공부 기록장

0개의 댓글

관련 채용 정보