[이코테] DFS/BFS - 미로 탈출 - JAVA

최영환·2022년 10월 17일
0

이코테

목록 보기
10/24
post-thumbnail

💡 문제

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력

  • 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력

첫째 줄에 최소 이동 칸의 개수를 출력한다.

💬 입출력 예시

입력

5 6
101010
111111
000001
111111
111111

출력

10

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// Queue 에 사용될 Node 클래스
class Node {
    private int x;
    private int y;

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

    /* Getter 메소드 */
    public int getX() {
        return this.x;
    }

    public int getY() {
        return this.y;
    }
}

public class dfs_bfs_02 {
    public static int n, m;
    public static int[][] graph = new int[201][201];

    // 이동방향 정의
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // n, m 입력
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 그래프 초기화
        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';
            }
        }

        // BFS 수행 결과 출력
        System.out.println(bfs(0, 0));
    }

    public static int bfs(int x, int y) {
        // Queue 구현을 위해 Queue 라이브러리 사용
        Queue<Node> q = new LinkedList<Node>();
        q.offer(new Node(x, y));

        // 큐가 빌 때 까지
        while(!q.isEmpty()) {
            Node node = q.poll();
            x = node.getX();
            y = node.getY();
            // 4 방향 확인
            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] == 0) {
                    continue;
                }
                // 이동 가능한 경우
                if (graph[nx][ny] == 1) {
                    graph[nx][ny] = graph[x][y] + 1;
                    q.offer(new Node(nx, ny));
                }
            }
        }
        // 탈출구(우측 최하단 위치)까지의 최단거리 반환
        return graph[n-1][m-1];
    }
}

📄 해설

  • BFS 를 사용하여 해결이 가능한 문제
  • 시작 지점인 (1,1) 은 (0,0) 으로 인덱스 처리를 하고, 해당 지점에서부터 BFS 를 수행하여 모든 노드의 값을 거리 정보로 넣으면 됨
profile
조금 느릴게요~

0개의 댓글