[백준] BOJ2178 - 미로탐색 (JAVA)

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

 

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

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

public class Solution
{

    static int n, m; //n*m 미로
    static int[][] arr; //미로 배열
    static boolean[][] visited; //방문체크
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    static void bfs(int x, int y){
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x,y));

        while(!queue.isEmpty()){
            Point tmp = queue.poll();
            int tmpX= tmp.x;
            int tmpY = tmp.y;

            for(int d=0;d<4;d++){ //네방향 탐색
                int nx = tmpX + dx[d];
                int ny = tmpY + dy[d];
                if(nx<0 || nx>=n || ny<0 || ny>=m) continue; // 범위가 미로보다 크면 continue
                if(visited[nx][ny] || arr[nx][ny]==0) continue; //이미 방문했거나 미로값이 0이면 continue
                queue.add(new Point(nx,ny)); //방문 후 큐에 추가
                visited[nx][ny] = true; //방문처리
                arr[nx][ny] = arr[tmpX][tmpY] + 1; //방문하면서 이전 값 +1
            }
        }
    }
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //BufferReader : 한줄을 통째로 입력받는 방법으로 주로 쓰인다.
        StringTokenizer st;
        //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine()); // readLine() : 값을 읽어올 때 String 값으로 개행문자(엔터값)을 포함해 한줄을 전부 읽어오는 방식 / read(): int 값으로 변형하여 읽어옴.
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        visited = new boolean[n][m];

        for(int i=0;i<n;i++){
            String tmp = br.readLine();
            for(int j=0;j<m;j++){
                arr[i][j] = tmp.charAt(j)-'0';
            }
        }

        bfs(0,0);
        System.out.println(arr[n-1][m-1]);

        //bw.flush();
        //bw.close();

    }
}

 

오랜만에 알고리즘 공부를 다시 시작했다. 꾸준히 해보자구.

오늘은 간단하게 bfs 문제를 풀어보았다 :) 

크게 어려운 부분은 없었던 간단한 문제 !