[이코테][Java] 미로 탈출

문제 설명

동빈이는 n × m 크기의 직사각형 형태의 미로에 갇혀 있다.

동빈이의 위치는 (1, 1), 미로의 출구는 (n, m)이고, 한번에 한 칸씩 이동할 수 있다.

미로에서 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어있을 때, 동빈이가 미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오.

(칸을 셀 때는 시작칸과 마지막칸을 모두 포함해서 계산한다.)

 

입력조건

• 첫째 줄에 정수 N, M
• 다음 N개의 줄에 각각 M개의 정수로 미로의 정보

출력조건

• 최소 이동 칸의 개수

입출력 예시

입력예시	출력예시
5 6 101010 111111 000001 111111 111111	10

 

 

 

 

문제 풀이

• 최소 칸의 개수를 구하기 위해서 BFS 알고리즘 사용
• 시작 지점에서 가까운 지점부터 차례대로 탐색하면서 값이 1일 경우
  1. queue에 해당 위치 값을 삽입
  2. (현재 칸의 값) = (이전 칸의 값) + 1 하여 방문처리를 하고, 시작 지점에서부터의 거리 값을 구함
• pair 클래스를 생성해서 queue에 x, y 두 개의 값을 삽입

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


class Pair{
    int x;
    int y;

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

public class Main {
    public static int n, m;
    public static int graph[][];
    public static Queue<Pair> q = new LinkedList<>();

    //상, 하, 좌, 우
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

    public static int bfs(int x, int y) {
        q.offer(new Pair(x, y));    //탐색 시작 노드를 큐에 삽입


        //큐가 빌 때까지 반복
        while(!q.isEmpty()) {
            Pair pair = q.poll();   //큐에서 현재 탐색 노드를 꺼냄
            x = pair.x;
            y = pair.y;

            //상, 하, 좌, 우로 탐색해서 이동할 수 있는 부분이 있는지 확인
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                //미로 공간을 벗어날 경우 무시
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    continue;
                }
                if (graph[nx][ny] == 1) {
                    graph[nx][ny] = graph[x][y] + 1;
                    q.offer(new Pair(nx, ny));
                }
            }
        }
        return graph[n-1][m-1];
    }


    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());


        graph = new int[n+1][m+1];
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        System.out.println(bfs(0, 0));
    }
}

---

 

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈