#2178. 미로탐색

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

1. 문제 이해

(0,0) 의 좌표부터 (m,n) 좌표 까지 이동할 때 최소경우의 수를 구하는 문제입니다.

2. 접근 방법

- 완전 탐색을 하되, 갔던곳을 다시 가지 않기 위해 큐를 사용해서 문제를 해결하고자 했습니다.

- 큐가 가지는 자료구조를 만들기 위해 Node라는 클래스를 만들었습니다.

3. 문제 해결

package SilverBell;
 
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 NoteString {
    public static int n;
    public static int m;
    public static int result;
    public static int map[][];
    public static int dx[] = { 1, 0, -1, 0 };
    public static int dy[] = { 0, 1, 0, -1 };
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        map = new int[n][m];
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            String tmp = st.nextToken();
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(tmp.substring(j, j+1));
            }
        }
        
        bfs(new Node(0, 0, 1));
        System.out.println(result);
    }
    
    public static void bfs(Node init) {
        Queue<Node> qu = new LinkedList<>();
        qu.offer(init);
        
        while(true) {
            if(qu.isEmpty()) break;
            int x = qu.peek().x;
            int y = qu.peek().y;
            int d = qu.peek().depth;
            
            if(x == m-1 && y == n-1) {
                result = d;
                break;
            }
            qu.poll();
            for(int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if(map[ny][nx] == 0) continue;
                
                map[ny][nx] = 0;
                qu.offer(new Node( nx, ny, d+1 ));
            }
        }
    }
}
 
class Node {
    int x, y;
    int depth;
    
    public Node(int x, int y, int depth) {
        this.x = x;
        this.y = y;
        this.depth = depth;
    }
}