[백준] 2178번 - 미로 탐색 (Java)(◎)

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

2178번: 미로 탐색

 

<문제분석>

1. 미로에서 처음에서 끝까지 가는 최단거리를 구하는 문제이다.

2. 미로 입력에 공백이 없으므로 한줄 씩 string 문자열로 받고, 한글자씩 배열로 저장한다.

3. 방문체크를 위한 visited 배열을 준비하고, 첫 시작인 (1, 1)을 true로 설정한다.

4. BFS 알고리즘으로 상/하/좌/우로 탐색해서 1이면 이동하고 0이면 스킵한다.

5. 최단거리를 구하기

  5-1.  map 배열의 다음 탐색지에 누적거리+1을 덮어쓰면서 이동한다.

  5-2. 이전 A[4][6]의 값이 10이라고 할 때, 다른 경로로 왔을 때 8+1이면 9로 업데이트 한다.

 

<코드구현 #1>

import java.util.*;

/*
[백준] 2178번 - 미로 탐색 (Java)
*/

public class Main {
    static int N, M;
    static int A[][];    
    static boolean visited[][];

    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        A = new int[N+1][M+1];
        for (int i=1; i<=N; i++) {
            String str = in.next();
            char ch[] = str.toCharArray();
            for (int j=1; j<=M; j++) {
                 A[i][j] = ch[j-1] - '0';
            }
        }
    }

    class Point {
        int x;
        int y;
        Point (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    
    void BFS(int x, int y) {
        Queue<Point> Q = new LinkedList<>();
        visited[x][y] = true;
        Q.offer(new Point(x, y));

        while (!Q.isEmpty()) {
            Point tmp = Q.poll();
            for (int i=0; i<4; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];

                // 스킵하는 조건문
                if (nx <= 0 || nx > N || ny <= 0 || ny > M) continue;
                if (A[nx][ny] == 0) continue;
                if (visited[nx][ny]) continue;
                // 다음 탐색지 업데이트
                Q.offer(new Point(nx, ny));
                visited[nx][ny] = true;
                // 다음 탐색지를 누적거리+1로 업데이트 함.
                A[nx][ny] = A[tmp.x][tmp.y]+1;
            }
        }
    }
        
    void Solve() {
        visited = new boolean[N+1][M+1];
        BFS(1, 1);
        System.out.println(A[N][M]);
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

 

<코드구현 #2>

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

public class Main {
    static int N, M;
    static boolean visited[][];
    static int map[][];
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};

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

    void BFS(int x, int y) {
        Queue<Node> Q = new LinkedList<>();
        Q.offer(new Node(x, y, 1));
        visited[x][y] = true;

        while (!Q.isEmpty()) {
            Node now = Q.poll();
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                // 가지치기
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (map[nx][ny] == 0) continue;
                if (visited[nx][ny]) continue;
                if (nx == N-1 && ny == M-1) {
                    System.out.println(now.len + 1);
                    return;
                }
                Q.offer(new Node(nx, ny, now.len+1));
                visited[nx][ny] = true;
            }
        }
    }
	void Solve() {
        BFS(0, 0);
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        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++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            for (int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(str.substring(j, j+1));
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}