백준(BOJ) 2667: 미로 탐색

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

 

BFS로 품. 객체지향 설계 2주차 과제와 연관된 문제라 풀어봄. Collection class에 요소로 배열을 넣고 그 각각의 배열에 y,x좌표를 넣는 방식이 익숙치 않았음.

 

왜 DFS가 아닌 BFS냐는 의문에 아직 정확히 답은 못하지만, DFS로도 풀수 있긴함. 하지만 한번 방문된 적이 있다면 다음에 다시 방문했을때 그것은 무조건 최단거리가 아님을 이용하는 것에서 DFS보다는 BFS가 적당할 것이라는 생각.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{

    public static void bfs(int[][]graph, int y, int x){
        int[]dy={-1,1,0,0};
        int[]dx={0,0,-1,1};
        int n=graph.length;
        int m=graph[0].length;
        Queue<int[]>q=new LinkedList<>();
        q.add(new int[]{y,x});
        boolean[][]visited=new boolean[n][m];
        visited[0][0]=true;
        while(!q.isEmpty()){
            int[]loc=q.poll();
            int curY=loc[0];
            int curX=loc[1];
            for (int i=0;i<4;i++){
                int nextY=curY+dy[i];
                int nextX=curX+dx[i];
                if(nextY<0 || nextX<0 || nextY>=n ||nextX>=m)
                    continue;
                if(visited[nextY][nextX]||graph[nextY][nextX]==0)//방문한좌표는 두번다시 방문하지 못하므로
                    //어떤 점에 처음방문하게 되면 그것이 최단거리가 되고 그 점은 방문처리가 되어 불필요한 좌표값의 증가를 막는다. 
                    continue;
                graph[nextY][nextX]=graph[curY][curX]+1;
                q.add(new int[]{nextY, nextX});
                visited[nextY][nextX]=true;
            }
        }


    }
    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());
        int[][]map=new int[n][m];

        for(int i=0;i<n;i++){
            String str=br.readLine();
            for(int j=0;j<m;j++){
                map[i][j]=str.charAt(j)-'0';
            }
        }
        bfs(map, 0,0);
        System.out.println(map[n-1][m-1]);
    }

}