[백준] 2178번 미로 탐색 JAVA (자바) 풀이

문제 2178(BFS)

 

 : N×M크기 미로

 

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

: 1 = 이동할 수 있는 칸

  0 = 이동할 수 없는 칸

 

: (1, 1) ~ (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구해라

  서로 인접한 칸으로만 이동할 수 있고 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다

 

 

[입력]

 :  첫째 줄에 두 정수 N, M (2 ≤ N, M ≤ 100)

 :  다음 N개의 줄에는 M개의 정수로 미로 

 

 [출력]

 :  첫째 줄에 지나야 하는 최소의 칸 수를 출력

 

 

 

 [문제접근]

 

• 좌표 사용 시 int[] 나 Point 사용
  
  → int[] 배열을 사용
  

  Queue<int[]> q = new LinkedList<>();
  q.add(new int[] {x,y});

  
  → Point 사용
  

  import java.awt.Point;
  
  Queue<Point> que = new LinkedList<>();
  que.add(new Point(x,y));

        Point 클래스는 좌표 상의 위치를 나타내는데 사용

 

• bfs는 dfs나 백트래킹 같이 재귀가 아니므로 종료조건과 재호출이 없고 해당 메서드 안에서 모두 해결하고 나온다
  

 

 

 [코드]

import java.io.*;
import java.util.*;
import java.awt.Point;
public class Main{
    static int dx[] = {0,0,-1,1};
    static int dy[] = {-1,1,0,0};
    static int arr[][],N,M;
    static boolean visit[][];
    static int count = 1;
    
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        visit = new boolean[N][M];
        
        for(int i =0; i<N; i++){
            String s = br.readLine();
            for(int j =0; j<M; j++){
                arr[i][j] = s.charAt(j)- '0';
            }
        }
        
        bfs(0,0);
        System.out.println(arr[N-1][M-1]);
    }
    
    static void bfs(int x, int y){
        Queue<Point> que = new LinkedList<>();
        que.add(new Point(x,y));
        visit[x][y]=true;
        
        while(!que.isEmpty()){
            Point p = que.poll();
            for(int i =0; i<4; i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(0<=nx && nx<N && 0<=ny && ny<M && !visit[nx][ny] && arr[nx][ny]>0){
                    que.add(new Point(nx, ny));
                    visit[nx][ny] = true;
                    arr[nx][ny] = arr[p.x][p.y] + 1;
                }
           }
        }
    }
}

 

 [해설]
     

 :  static int dx[] = {0,0,-1,1};  움직일 x좌표
    static int dy[] = {-1,1,0,0};  움직일 y좌표
    static int arr[][],N,M;  
    static boolean visit[][];
    
 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());  입력받은 x좌표
    M = Integer.parseInt(st.nextToken());  입력받은 y좌표
    arr = new int[N][M];  지도
    visit = new boolean[N][M];  방문기록 초기화
        
 :  for(int i =0; i<N; i++){
         String s = br.readLine();  StringToken을 사용하지 않는 것은
          for(int j =0; j<M; j++){
                arr[i][j] = s.charAt(j)- '0';  문자를 숫자로 변환 
          }
    }
       

 :  bfs(0,0);  bfs 돌리기 
    System.out.println(arr[N-1][M-1]);  거리 출력  
    
    
 :  static void bfs(int x, int y){  
        Queue<Point> que = new LinkedList<>();  큐 선언
        que.add(new Point(x,y));  큐에 추가
        visit[x][y]=true;  방문 바로 체크
        
        while(!que.isEmpty()){
            Point p = que.poll();  큐에서 (x,y) 좌표 빼기
            for(int i =0; i<4; i++){
                int nx = p.x + dx[i];  현재 입력은 좌표 + 새로 이동
                int ny = p.y + dy[i];  현재 입력은 좌표 + 새로 이동
                if(0<=nx && nx<N && 0<=ny && ny<M && !visit[nx][ny] && arr[nx][ny]>0){  
                    que.add(new Point(nx, ny));  큐에 새로운 좌표 추가
                    visit[nx][ny] = true;  새 좌표 방문 체크
                    arr[nx][ny] = arr[p.x][p.y] + 1;  현재 거리에서 + 1
                }
            }
        }
    }


 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

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