[백준-2178]-[BFS]-미로탐색

문제 링크 : https://www.acmicpc.net/problem/2178

이문제는 BFS DFS 모두 풀 수 있다.

하지만 본인은 BFS로 풀었다. 

굳이 DFS로 풀지 않은 이유는 BFS가 더 땡기고 아직은 재귀적 생각이 짧아서 효율적인 재귀 함수를 구현을 잘 못하겠어서도 있다.

좀 더 공부를 하면서 시간을 단축하는 DFS를 작성할 수 있었으면 좋겠다.

이문제는 앞서 있는 다른 BFS 문제에 비해 매우 쉬운 난이도이다. 

각 칸을 BFS로 접근하면서 칸 수만 세면 끝나기 때문이다. 

벽에 도달하면 패스하고 방문한 이력이 있으면 패스하면 된다. 

한번이라도 방문을 했으면 무조건 적으로 먼저 방문했을때의 값이 작다. 

BFS는 Queue에 쌓아 하나씩 선입선출로 꺼내 사용하기 때문에 level 단위로 처리된다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static int row;
    public static int col;
    public static int step = Integer.MAX_VALUE;
    
    public static int[][] miro;
    public static boolean[][] visited;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        
        miro = new int[row+1][col+1];
        visited = new boolean[row+1][col+1];
        
        for(int i=1; i <=row; i++) {
            String str = br.readLine();
            for(int j=1; j <= col; j++) {
                miro[i][j] = Integer.parseInt(str.substring(j-1, j));
            }
        }
        
        BFS();
        System.out.println(step);
    }
    
    public static void BFS() {
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[] {1, 1, 1});
        
        while(!queue.isEmpty()) {
            int y = queue.peek()[0];
            int x = queue.peek()[1];
            int cnt = queue.peek()[2];
            queue.poll();
            
            // 좌표가 범위를 벗어나면 패스
            if(y < 1 || x < 1 || y > row || x > col) continue;
            // 이동할 수 없는 칸이거나 한번 방문했으면 그것또한 패스
            if(miro[y][x] == 0) continue;
            if(visited[y][x])continue;
            
            // 목표 좌표에 도달했으면 스텝수를 확인
            if(y == row && x == col) {
                if(step > cnt) step = cnt;
                continue;
            }
            // 방문여부를 변경한다.
            visited[y][x] = true;
            
            // 다음 좌표로 이동한다.
            queue.offer(new int[] {y-1, x, cnt+1});
            queue.offer(new int[] {y+1, x, cnt+1});
            queue.offer(new int[] {y, x-1, cnt+1});
            queue.offer(new int[] {y, x+1, cnt+1});
        }
    }
}