[BAEKJOON_2178 - JAVA] 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

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

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

해결 과정

최단 경로 찾기의 경우 DFS로는 시간초과의 확률이 크기 때문에 처음부터 BFS로 접근.
위치 class를 만들어 관리를 편리하게 진행.
메모리 초과가 지속적으로 발생해 고민한 결과
visited 함수 true를 시켜주는 문장의 위치가 문제임을 파악.
push와 동시에 visited를 체크하여, 중복적인 visited 체크를 방지. 

 

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class location {
    int row;
    int col;
 
    public location(int row, int col) {
        super();
        this.row = row;
        this.col = col;
    }
}
 
public class Main {
 
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int[] dy = { -1, 1, 0, 0 }; // 상하좌우
    static int[] dx = { 0, 0, -1, 1 };
 
    // 범위 검사
    static boolean isValid(int i, int j) {
        if (i < 0 || j < 0 || i >= N || j >= M) {
            return false;
        }
        return true;
    }
 
    static void solution(int row, int col) {
        Queue<location> q = new LinkedList<location>();
        q.offer(new location(row, col));
        visited[row][col] = true;
        while (!q.isEmpty()) {
            location loc = q.poll();
            //visited[loc.row][loc.col] = true; 초기 방문체크 위치
 
            for (int i = 0; i < 4; i++) {
                int nexty = loc.row + dy[i];
                int nextx = loc.col + dx[i];
 
                if (!isValid(nexty, nextx) || visited[nexty][nextx] || map[nexty][nextx] == 0) // 범위
                    continue;
 
                map[nexty][nextx] = map[loc.row][loc.col] + 1;
                visited[nexty][nextx] = true;
                q.offer(new location(nexty, nextx));
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];
 
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
 
        // ============================== 입력 ==============================
        solution(0, 0);
        System.out.println(map[N - 1][M - 1]);
    }
 
}
 

 

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색