백준 2178 미로탐색 JAVA

solved.ac 티어 = 실버 1

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

2178번: 미로 탐색

 

가중치 없는 그래프에서 최단 거리를 구하는 가장 기초적인 BFS 문제다.

 

1. 접근

 

미로의 모든 칸을 다 밟는다고 가정해도 최대 N * M, 즉 100²인 10,000으로 시간제한 1초 내에 풀 수 있다.

 

이동할 때의 조건으로는 다음과 같으며 배열로 미리 저장해두면 다음과 같으며

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

 

좌표상 (n - 1)(m - 1)에 도착했을 때 이동한 최단거리를 출력하면 된다.

 

2. 풀이

 

예제의 표를 정답을 구하기 위해 누적하며 진행한다면 다음과 같다.

1	0	9	10	11	12
2	0	8	0	12	0
3	0	7	0	13	14
4	5	6	0	14	15

 

즉 여타 다른 BFS 문제처럼 방문 여부, 배열 범위 여부, 방문 가능 여부(문제에선 1인지 0인지)를 판별하여

해당 위치의 값을 int[][] 형태로 이전 값 + 1씩 누적하다 요구사항인 N, M 칸을 출력하기만 하면 된다.

 

전역 변수 및 input

static int N, M;
static int[][] dist; // 이동횟수 기록
static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 다음 방문좌표
static String[] A; // input
public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    dist = new int[N][M];

    A = new String[N];
    for (int i = 0; i < N; i++) {
        A[i] = br.readLine();
    }
    solution();
}

 

배열 초기화 및 BFS 호출

static void solution() {
    for (int i = 0; i < N; i++) {
        Arrays.fill(dist[i], -1); // 배열 초기화
    }
    BFS(0, 0); // (0, 0) 좌표부터 확인하자!
    System.out.println(dist[N - 1][M -1]); // N, M에 도착했을 때 이동 횟수를 출력
}

 

BFS

static void BFS(int x, int y) {
    Queue<Integer> Q = new LinkedList<>();
    Q.add(x); // x좌표
    Q.add(y); // y좌표
    dist[x][y] = 1; // 문제에선 시작칸도 체크한다.

    while(!Q.isEmpty()) {
        x = Q.poll();
        y = Q.poll();
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue; // 배열범위 안인지?
            if (A[nx].charAt(ny) == '0') continue; // 방문할 수 있는 칸인지?
            if (dist[nx][ny] != -1) continue; // 이미 방문했는지?
            dist[nx][ny] = dist[x][y] + 1; // 한 칸 전진했으니 이전값 + 1을 한다.
            Q.add(nx);
            Q.add(ny);
        }
    }
}

 

3. 전체코드

 

 

코드나 풀이 방식에 대한 지적은 환영합니다!