백준 2178 - 미로탐색 (JAVA 자바)

백준 2178 - 미로탐색 (JAVA)

BFS로 풀었습니다.

생각보다 처리할 것이 많습니다. 

 

www.acmicpc.net/problem/2178

 

 

 

 

 

 

 

 

1. N*M 바둑판에 대한 정보가 String으로 주어집니다. 이에 대한 처리가 필요합니다.

2. 1번에 대한 정보가 한줄에 전부 String으로 붙어져서 제공됩니다. 한글자씩 짤라서 저장해두어야 합니다.

 

 

 

 

import java.util.*;
 
public class Main {
 
    static int n,m,cnt;
    static char map[][];
    static int visits[][];
    static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt(); //4
        m = sc.nextInt(); //6
        cnt = 0;
        
        map = new char [n+2][m+2];
        for(int i=0; i<=n+1; i++) {
            for(int j=0; j<=m+1; j++) {
                map[i][j] = '0';
            }
        }
        
        visits = new int [n+2][m+2];
        
        for(int i=1; i<=n; i++) { //4
            String temp1 = sc.next();
//            System.out.println("temp1값은 : " + temp1);
            for(int j=1; j<=m; j++) { //6
                char temp2 = temp1.charAt(j-1);
//                System.out.println("temp2 값은 : " + temp2);
                map[i][j] = temp2;
//                System.out.println(map[i][j] + " ");
            }
        }
        
        
//        for(int i=0; i<=n+1; i++) {
//            for(int j=0; j<=m+1; j++) {
//                System.out.print(map[i][j] + " ");
//            }System.out.println();
//        }
        
        bfs(1,1);
    }
    
    
    private static void bfs (int x, int y) {
        visits[x][y] = 1;
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(x); // x좌표 제공
        q.offer(y); // y 좌표 제공
        
        while(!q.isEmpty()) {
            int out1 = q.poll();
            int out2 = q.poll();
            
            for(int i=0; i<4; i++) {
                
                if(out1+dx[i]>=0 && out2+dy[i]>=0 && out1+dx[i]<=n && out2+dy[i]<=m) { // 범위를 벗어나면 아래 로직을 타지 않는다.
                    int new_x = out1+dx[i]; // 새로운 x좌표
                    int new_y = out2+dy[i]; // 새로운 y좌표
                    if(visits[new_x][new_y]==0 && map[new_x][new_y] == '1') {
                        visits[new_x][new_y] = visits[out1][out2]+1;
                        q.offer(new_x);
                        q.offer(new_y);
//                        System.out.println("new_x 값은 : " + new_x + ", new_y값은 : " + new_y + ", visits[out1][out2] 값은 : " + visits[out1][out2]);
                    }
                }
            }
        }
        
        System.out.println(visits[n][m]);
    }
}