[BOJ] 14940 : 쉬운 최단거리 (Java)

 

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

14940번: 쉬운 최단거리

걸린 시간 : 34분 33초

---

알고리즘

최단 거리 알고리즘 중 어떤 알고리즘?

최단 거리를 구할 수 있는 알고리즘 중 4가지를 살펴보자.

	어떤 한 시작점에서 출발할 경우	모든 시작점을 다 고려할 경우
가중치가 없는 경우	BFS 알고리즘	BFS or 플로이드 알고리즘
가중치가 있는 경우	다익스트라 알고리즘	플로이드 알고리즘

 

이렇게 4가지를 생각하면 어떤 문제에서 어떤 알고리즘을 써야할지 쉬울 것이다.

이 문제는 주변 칸까지의 거리가 모두 1이므로 가중치가 없다.

또한 도착점이 있지만, 역으로 생각해 도착점에서 모든 정점까지 거리를 구해도 되므로 한 시작점에서 시작한다고 생각해도 좋다.

따라서 BFS 알고리즘을 쓰자.

Pseudo Code

BFS의 대략적인 Pseudo Code는 다음과 같다.

board, dist, queue 선언 및 입력;
int di[], dj[] 선언;
dist배열을 모두 -1로 fill;
// 1. 시작점 처리
queue에 시작노드 삽입;
시작노드 dist를 0으로;
while (!q.empty()) {
	// 2. 현재 노드 처리
    int ci, cj = q.top();
    q.pop();
    for (int k = 0; k < 방향 가짓수; k++) {
        // 3. 다음 노드 처리
        int ni, nj = ci + di[k], cj + dj[k];
        // 4. 방문할 것인지
        if (ni와 nj가 범위안에 없다 || 갈 수 없는 곳(벽)이다 || 방문했다) continue; //여기서 방문했는지를 dist[ni][nj]가 -1인지로 체크
        // 5. 방문 처리
        큐에 nx, ny 삽입;
        dist[nx][ny] 최신화;
    }
}

 

하지만, 이 문제의 끝 조건때문에 이와 같은 코드를 사용할 수 없다. 즉, dist 배열로 방문체크를 할 수 없다.

vis 배열을 따로 만들어 방문체크를 해야 한다.

board, dist, visited, queue 선언 및 입력;
int di[], dj[] 선언;
// 1. 시작점 처리
queue에 시작노드 삽입;
시작노드 visited 체크;
while (!q.empty()) {
	// 2. 현재 노드 처리
    int ci, cj = q.top();
    q.pop();
    for (int k = 0; k < 방향 가짓수; k++) {
        // 3. 다음 노드 처리
        int ni, nj = ci + di[k], cj + dj[k];
        // 4. 방문할 것인지
        if (ni와 nj가 범위안에 없다 || 갈 수 없는 곳(벽)이다 || 방문했다) continue;
        // 5. 방문 처리
        visited에 [ni][nj] 방문처리;
        큐에 nx, ny 삽입;
        dist[nx][ny] 최신화;
    }
}

 

이런 코드는 굉장히 자주 나오기 때문에 툭 치면 나올 정도로 외운다.

위처럼 dist배열만을 사용할 땐 방문처리할 때 2가지 일(큐 삽입, 거리 최신화)을 하고, vis배열까지 사용할 땐 방문처리할 때 3가지 일(큐 삽입, 거리 최신화, 방문처리)을 한다.

맨 처음에 설정할 때는 반대로 dist배열만을 사용할 땐 3가지 일(dist배열을 -1로 fill, 시작점 큐 삽입, 시작점 dist를 0으로)을 하고, vis배열까지 사용할 땐 2가지 일(시작점 큐 삽입, 시작점 방문처리)만을 한다.

정답 코드

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

public class BOJ14940 {

    static int n, m;
    static int[][] board = new int[1001][1001];
    static int[][] dist = new int[1001][1001];
    static boolean[][] vis = new boolean[1001][1001];
    static int[] di = {-1, 0, 0, 1};
    static int[] dj = {0, -1, 1, 0};
    static Queue<Pos> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        Pos startPos = null;
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 2) {
                    startPos = new Pos(i, j);
                }
            }
        }
        vis[startPos.i][startPos.j] = true;
        q.offer(startPos);
        while (!q.isEmpty()) {
            Pos cur = q.poll();
            for (int k = 0; k < 4; k++) {
                Pos next = new Pos(cur.i + di[k], cur.j + dj[k]);
                if (next.i < 0 || next.i >= n || next.j < 0 || next.j >= m
                        || board[next.i][next.j] == 0 || vis[next.i][next.j])
                    continue;
                q.offer(next);
                vis[next.i][next.j] = true;
                dist[next.i][next.j] = dist[cur.i][cur.j] + 1;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1 && dist[i][j] == 0) {
                    System.out.print(-1 + " ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    static class Pos {
        int i, j;

        Pos(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}