백준 2178번 미로탐색 (based on JAVA)

 

 

1. 문제

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

2. 입출력 데이터

Input Data	Output Data
4 6 101111 101010 101011 111011	15

3. 문제 요약

시작점은 항상 0,0 에서 출발하고 N x M 크기의 미로에 끝점에 도착해야함
단, 0 인 숫자는 지나갈 수 없고, 도착점까지 거리 중 최소값을 반환하도록 해야함!

 

 

 

4. 문제풀이

0) 필요한 라이브러리 및 프레임워크 static으로 정의

// 미로 정보를 받을 2차원 int 배열
static int[][] grid;

// 현재 node 위치에서 4방향 값을 확인하기위해 directionX, directionY 정의
static int[] directionX = {1, 0, -1, 0};
static int[] directionY = {0, 1, 0, -1};

// 방문처리를 위한 2차원 boolean 배열 정의
static boolean[][] visited;

// 최소 거리를 구하기 위한 ArrayList 정의
static ArrayList<Integer> minDistance = new ArrayList<>();

 

 

 

 

1) 입력 데이터 받아 처리하기

ㄱ. BufferedReader 를 이용해 한줄씩 문자열을 입력받음
ㄴ. StringTokenzier를 이용해 입력받은 문자열을 자르고 보관
ㄷ. 첫번째 받은 문자열 데이터는 미로 크기를 결정함으로 각 각 int N, M 으로 초기화해줌
ㄹ. 미로(grid) 크기는 2차원 배열로 정의 : int[][] grid =  new int[N][M]
ㅁ. 방문처리를 위한 visited 2차원 배열 정의 : boolean[][] visited = new boolean[N][M]
ㅂ. 미로 정보 문자열을 BufferedReader로 한줄씩 받아 split해 문자열 배열로 초기화
ㅅ. Stream을 이용해 split한 문자열을 Int로 변환하고 1차원 int 배열(int[] row)로 초기화
ㅇ. 초기화한 1차원배열(int[] row)을 grid에 할당

 

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        grid = new int[N][M];
        visited = new boolean[N][M];

        // 입력받은 문자열을 2차원 int 배열로 변환하기
        for (int i = 0; i < N; i++) {

            String[] s = br.readLine().split(""); // 입력받은 문자열을 한개씩 잘라 문자열배열로
            int[] row = Stream.of(s).mapToInt(Integer::parseInt).toArray(); // 문자열배열을 int[] 배열로
            grid[i] = row; // int[] 배열을 선언된 grid[][] 에 할당

        }

 

 

 

 

2) BFS 함수 정의

 

ㄱ. BFS 문제풀를 위해 Queue 초기화
ㄴ. 시작 노드 정의 : int[][] startNode = new int[][]{0,0]}
ㄷ. 시작 노드 방문처리
ㄹ. 시작노드를 Queue에 담기 : q.offer(startNode)
ㅁ. Queue 가 빌때까지 while문 반복
ㅂ. Queue 에 담긴 노드를 뽑아 currentNode에 초기화
ㅅ.  currentNode 기준 4방향 확인 (for문 반복 횟수를 4로 한 이유임)
     - currentNode 좌표를 각 각 currentX, currentY에 초기화
     - 앞에서 정의한 directionX, directionY를 이용해 nextNodeX, nextNodeY를 초기화
     - 조건식을 이용해 4방향에 데이터가 없는 경우 걸러냄(앞서 정의한 2차원 배열 grid length 값을 이용!!)
ㅇ. 다음 노드위치는 조건식으로 처리함
     - 목표 노드 위치 일 경우 : minDistance Arraylist에 지금까지 더해온 거리값을 담기
     - 다음 이동할 노드의 2차원 배열 grid[nextNodeY][nextNodeX] 값에 거리값을 하나씩 더해가기(아래 그림 참고)
     - 다음 이동할 노드 좌표를 Queue에 담아주기
     - 현재 노드는 방문처리

 

 

 

static void bfs(){

        Queue<int[][]> q = new LinkedList<>();

        int[][] startNode = new int[][]{{0, 0}};

        // 첫번째 노드 방문처리
        visited[0][0] = true;
        q.offer(startNode);

        while (!q.isEmpty()) {

            int[][] currentNode = q.poll(); // 0,0 = 1

            // 4 방향 확인
            for (int i = 0; i < 4; i++) {

                int currentX = currentNode[0][1];
                int currentY = currentNode[0][0];

                int nextNodeX = currentX + directionX[i]; // 1, 0, -1, 0
                int nextNodeY = currentY + directionY[i]; // 0, 1, 0, -1

                // 4방향 노드 위치중 벽(값이 없음) 경우 제외
                if (nextNodeX < 0 || nextNodeY < 0 || nextNodeX > grid[0].length - 1 || nextNodeY > grid.length - 1 ) {
                    continue;

                }

                if (grid[nextNodeY][nextNodeX] == 1 && !visited[nextNodeY][nextNodeX]) {

                    // 목표 노드에 도착했을 때
                    if (nextNodeX == grid[0].length-1 && nextNodeY == grid.length-1 ) {
                        minDistance.add((grid[currentY][currentX] + 1));
                        continue;
                    }
					
                    // 거리 값 더해주기
                    grid[nextNodeY][nextNodeX] = grid[currentY][currentX] + 1;
                    
                    // 다음 이동할 노드 데이터 큐에 담기
                    q.offer(new int[][]{{nextNodeY, nextNodeX}});
					
                    // 현재 노드 위치 방문처리
                    visited[currentY][currentX] = true;
                }

            }


        }

 

 

3) 거리값중 최소값 출력

목표 노드에 도착했을 경우에 ArrayList에 거리값을 담아줬었음
BFS 함수 종료 후 minimum 값을 아래 코드와 같이 구현

        int min = minDistance.get(0);
        for (int i = 1; i < minDistance.size(); i++) {

            if (min > minDistance.get(i)) {
                min = minDistance.get(i);
            }

        }

        System.out.println("min = " + min);

 

 

5. 최종 작성한 코드

 

package BFS.실전문제.BAEKJUN;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Stream;

public class 미로탐색 {


    static int[][] grid;

    static int[] directionX = {1, 0, -1, 0};
    static int[] directionY = {0, 1, 0, -1};

    static boolean[][] visited;
     static ArrayList<Integer> minDistance = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        /**
         * 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때,
         * (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.
         * 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
         *
         * 입력
         * 4 6 // 두 정 수 N, M
         * 101111 // 미로 데이터
         * 101010
         * 101011
         * 111011
         *
         * 출력 // 1,1 부터 n,m 까지 갈 때 최소 칸의 수 출력
         * 15
         */

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        grid = new int[N][M];
        visited = new boolean[N][M];

        // 입력받은 문자열을 2차원 int 배열로 변환하기
        for (int i = 0; i < N; i++) {

            String[] s = br.readLine().split(""); // 입력받은 문자열을 한개씩 잘라 문자열배열로
            int[] row = Stream.of(s).mapToInt(Integer::parseInt).toArray(); // 문자열배열을 int[] 배열로
            grid[i] = row; // int[] 배열을 선언된 grid[][] 에 할당

        }

        bfs();


        int min = minDistance.get(0);
        for (int i = 1; i < minDistance.size(); i++) {

            if (min > minDistance.get(i)) {
                min = minDistance.get(i);
            }

        }

        System.out.println("min = " + min);

    }

    static void bfs(){

        Queue<int[][]> q = new LinkedList<>();

        int[][] startNode = new int[][]{{0, 0}};

        // 첫번째 노드 방문처리
        visited[0][0] = true;
        q.offer(startNode);

        while (!q.isEmpty()) {

            System.out.println("********* while문 시작 **********");

            int[][] currentNode = q.poll(); // 0,0 = 1
            System.out.println("currentNode = " + Arrays.deepToString(currentNode));

            // 4 방향 확인
            for (int i = 0; i < 4; i++) {
                System.out.println(" =========================== for문 시작 ========================");
                System.out.println(i+"번째 출력");

                int currentX = currentNode[0][1];
                int currentY = currentNode[0][0];

                System.out.println("currentY = " + currentY);
                System.out.println("currentX = " + currentX);


                int nextNodeX = currentX + directionX[i]; // 1, 0, -1, 0
                int nextNodeY = currentY + directionY[i]; // 0, 1, 0, -1

                System.out.println("nextNodeY = " + nextNodeY);
                System.out.println("nextNodeX = " + nextNodeX);

                // 현재 노드 기준
                // 남쪽 grid[1][0] = 1,               동쪽 grid[0][1] = 0
                // 북쪽 gird[-1][0] = outOfIndex,     서쪽 grid[0][-1] = outOfIndex

                // 옆이 벽면일 경우 제외
                if (nextNodeX < 0 || nextNodeY < 0 || nextNodeX > grid[0].length - 1 || nextNodeY > grid.length - 1 ) {
                    System.out.println("@@@ 옆면이 벽면임 @@@︎︎︎");
                    continue;

                }

                System.out.println("grid[nextNodeY][nextNodeX] = " + grid[nextNodeY][nextNodeX]);
                // i=0, nextX = 1, nextY = 0

                /**
                 *  101111 // 미로 데이터
                 *  101010
                 *  101011
                 *  111011
                 */
                if (grid[nextNodeY][nextNodeX] == 1 && !visited[nextNodeY][nextNodeX]) {
                    System.out.println("----------"+i+"번째 큐에 넣는 조건 검사중!!----------");
                    System.out.println("nextNodeY = " + nextNodeY);
                    System.out.println("nextNodeX = " + nextNodeX);

                    System.out.println("grid[0].length = " + grid[0].length);
                    System.out.println("grid.length = " + grid.length);

                    // 목표 노드에 도착했을 때
                    if (nextNodeX == grid[0].length-1 && nextNodeY == grid.length-1 ) {
                        System.out.println("** last grid[currentY][currentX] = " + (grid[currentY][currentX] + 1));
                        minDistance.add((grid[currentY][currentX] + 1));
                        continue;
                    }

                    grid[nextNodeY][nextNodeX] = grid[currentY][currentX] + 1;
                    q.offer(new int[][]{{nextNodeY, nextNodeX}});

                    System.out.println("q에 nextNode 닮긴값 ==> ["+nextNodeY+"]["+nextNodeX+"]" );
                    visited[currentY][currentX] = true;
                }

                System.out.println(" R=========================== for문 종료 ========================");
                System.out.println();
            }

            System.out.println("********* while문 진행 중  **********");
            System.out.println();

        }

        System.out.println("********* while문 종료 **********");


    };
}

 

 

 

※ 시행착오 및 느낀점

BFS 함수를 정의하면서 4방향중 한 방향이 아닌 2~3 방향으로 이동이 가능할 경우 어떻게 처리해야할지 고민했었음.
처음에는 별도 조건없이 도착노드 좌표까지 큐에 담도록 하고, 별도의 count 변수를 정의해 q 에 담길때마다 + 1을 해주도록 구현 했었다.

하지만, 모든 1인 미로를 더하는 것과 다를바 없어 최소 거리를 구하지 못했고, 이를 해결하고자 ArrayList를 이용했다.
다음 이동할 노드가 목표 노드 좌표일 경우 더이상 큐에 담지 않고, continue로 넘기고, 현재까지 이동한 거리를 Arraylist에 담도록 구현하고, BFS 함수가 종료했을 때 ArrayList를 이용해 최소 거리를 출력하도록 구현했다.

알고리즘 문제를 처음 이해하는데는 많은 시간이 필요하나, 시행착오를 겪으면서 최종 답을 도출했을때의 쾌감은 이루말할수 없는 것 같다.