[백준] 2178번 미로 탐색 - BFS / 너비 탐색 알고리즘 / 클래스

문제

 

 

My Code

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

class ArrGraph{
    private int[][] arrGrapgh; //인접 행렬 선언
    boolean[][] visit; // 방문 배열 선언
    private int n, m; //행과 열 선언
    
    //상하좌우 탐색 배열 선언 및 초기화
    private int[] dx = {0, 1, 0, -1}; 
    private int[] dy = {1, 0, -1, 0};

    //생성자
    public ArrGraph(int n, int m) {
        this.arrGrapgh = new int[n][m];
        this.visit = new boolean[n][m];
        this.n = n;
        this.m = m;
    }
    
    //인접 행렬에 값 저장
    public void put(String str, int i) {
        for (int j = 0; j < str.length(); j++) {
            arrGrapgh[i][j] = Integer.parseInt(str.split("")[j]);
        }
    }
    
    //bfs 실행
    public void bfs(int i, int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i, j});
        while(!queue.isEmpty()){
            int[] now = queue.poll(); 
            visit[i][j] = true;
            for (int k = 0; k<4; k++){ // 상하좌우 탐색
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if(x >= 0 && y >= 0 && x < n && y <m){ //인접 행렬의 범위에 맞게
                    if (arrGrapgh[x][y] != 0 && !visit[x][y]){ 
                        visit[x][y] = true;
                        arrGrapgh[x][y] = arrGrapgh[now[0]][now[1]] + 1; // 1번 움직이면 depth + 1
                        queue.add(new int[] {x, y});
                    }
                }
            }
        }
    }
    
    // 결과 출력
    public void printResult(){
        System.out.println(arrGrapgh[n-1][m-1]);
    }
}

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        // 행과 열 입력 받기
        String strNM = bf.readLine();
        int n = Integer.parseInt(strNM.split(" ")[0]);
        int m = Integer.parseInt(strNM.split(" ")[1]);

        // 인접 행렬 선언 및 크기 설정
        ArrGraph arrGraph = new ArrGraph(n, m);

        // 인접 행렬의 한 행씩 저장
        for (int i = 0; i < n; i++){
            String strArr = bf.readLine();
            arrGraph.put(strArr, i);
        }

        arrGraph.bfs(0, 0);
        arrGraph.printResult();
    }
}

 

 

문제의 핵심 & 알게된 점

이 문제는 인접노드를 한번에 탐색하는 BFS를 이용하는게 효율적이다.

이때 인접 노드의 값에 +1을 해준다면

그 깊이에 따라 갖는 값이 같아지기 때문에

결과를 도착 위치(n-1, m-1)의 인접 행렬 값으로 출력하면 된다. 

입력

인접 행렬 결과

이 논리는 위의 결과로 설명이 가능하다.

한 칸씩 이동할 때마다 +1 한다고 생각하면 간단하다.

 

인접 행렬은 2차원 배열이다 보니 Queue에 어떻게 삽입할 지 고민이었는데 

queue.offer(new int[] {i, j});

위와 같은 방식으로 삽입이 가능하단 걸 알게 되었다.

 

상하 좌우로 탐색하는 부분을 switch 또는 if문으로 해야하나 고민이었는데

dx, dy 배열을 선언해서 for반복문을 사용하는 방식을 알게되어 효율적으로 작성할 수 있었다.

 

 

 

참고 강의_인프런의 Do it! 알고리즘 코딩테스트 with JAVA