[백준 BFS] 2178번: 미로탐색 (Java)

package main;

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {

        //입력 배열 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int y = Integer.parseInt(firstLine[0]);
        int x = Integer.parseInt(firstLine[1]);
        int[][] arr = new int[y][x];

        //배열 채우기
        for(int i=0; i<y; i++){
            String line = br.readLine();
            for(int j=0; j<x; j++){
                arr[i][j] = line.charAt(j) - '0';
            }
        }

        //필요한 필드 선언
        Pair startP = new Pair(0,0, 1);
        arr[0][0] = 0; //시작 배열 방문 처리

        //인접한 인덱스에 접근하기 위한 필드
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        //BFS 전용 큐
        Queue<Pair> Q = new ArrayDeque<>();
        Q.add(startP);

        while(true){
            //큐에서 가장 앞단 데이터 삭제
            Pair removeP = Q.poll();

            //종료 조건 : 큐에서 빼낸 x, y의 인덱스가 도착 지점일 때
            if(removeP.x==x-1 && removeP.y==y-1) {
                System.out.println(removeP.distance);
                break;
            }

            //큐에서 제거한 요소의 인접 인덱스 접근
            for(int i=0; i<4; i++){
                int nx = removeP.x + dx[i];
                int ny = removeP.y + dy[i];

                //인접 인덱스 유효성 검사
                if((nx<0||ny<0) || (nx>=x||ny>=y) || arr[ny][nx]==0) continue;

                //유효성 검사에서 통과한 인덱스에 대해 요소 생성, 거리 = 제거한 요소의 거리 + 1
                Pair next = new Pair(nx, ny, removeP.distance+1);
                
                //새로운 요소의 좌표 방문 처리
                arr[ny][nx] = 0;
                Q.add(next);
            }
        }
    }
    
    static class Pair{
        int x;
        int y;
        int distance;

        public Pair(int x, int y, int distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }
}

 

최단 거리를 구하는 BFS 유형의 문제이다.

Pair 클래스에 좌표와 함께 distance 파라미터를 넣었다.

좌표 상에서 두 갈래 길로 나뉘어지고 Pair 객체끼리 서로 다른 distance를 가지게 되더라도

while문의 종료 조건으로 마지막 좌표에 먼저 도착하는 객체의 distance를 출력하고 메인 함수를 종료하기 때문에

올바른 답이 출력된다.