Path Finder #2: shortest path, CodeWars Kata 자바 솔루션

 

Path Finder #2: shortest path, CodeWars Kata

Path Finder #2: shortest path

사진: 코드워즈

Task

You are at position [0, 0] in maze NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return the minimal number of steps to exit position [N-1, N-1] if it is possible to reach the exit from the starting position. Otherwise, return -1.

Empty positions are marked .. Walls are marked W. Start and exit positions are guaranteed to be empty in all test cases.

문제 해설

개행문자로 구분된 N*N의 행렬이 입력값으로 제공됩니다. 행렬은 .과 W로 이루어져 있으며 .는 이동할 수 있는 칸을 의미하고 W는 벽, 즉 이동할 수 없는 칸을 의미합니다. 우리는 [0, 0] 위치에서 시작해서 [N-1, N-1]에 도달하는 가장 짧은 경로의 길이를 구해야 합니다.

입력값

• String maze: 개행문자로 구분된 .과 W로 이루어진 N*N의 행렬

출력값

• int result: [N-1, N-1]에 도달하는 가장 짧은 경로의 길이, 도달할 수 없으면 -1을 리턴.

 

My Solution

Path Finder #1:Can you reach the exit과 유사하지만 길이를 구해야 한다는 점이 다릅니다. 먼저 1번과 유사하게 2번에서도 입력 문자열을 2차원 배열로 변환하지 않고 갯수만 센 후 개행문자를 제거하여 1차원 배열로 다뤘습니다. 각각의 칸을 그래프의 정점으로 보고 인접한 칸으로 이동 가능하다면 간선이 존재하는 것으로 간주했습니다.

먼저 LinkedList<Integer>[] link 를 생성해 간선을 모두 입력했습니다. 하나의 칸을 기준으로 동서남북 칸으로 이동 가능한 지 체크 한 후 이동 가능한 칸들을 담아줍니다.

그 다음은 거리를 구하는 메소드 void getDistance(LinkedList<Integer>[] link, int[] distances, int start, int dest)를 정의했습니다. int[] distances는 각각의 정점에 도달하는 거리를 담습니다. 초기값은 N*N(도달할 수 없을 경우)으로 지정했습니다.

이번 문제는 큐를 이용해 풀었습니다. LinkedList<int[]> queue에 먼저 시작점에서 연결된 지점들을 모두 넣은 후 하나 하나 탐색을 합니다. 다익스트라 알고리즘처럼 어느 정점에 도달하게 되면 거리를 갱신해 줍니다. 모든 루트를 파악해 갱신이 끝나고 나면 distances[N * N - 1]에 거리가 담겨 있게 됩니다.

솔루션 코드

테스트 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.stream.IntStream;

public class Finder {

  public static int pathFinder(String maze) {
        int N = maze.indexOf("\n");
        maze = maze.replaceAll("\n", "");

        if (maze.length() == 1)
            return 0;

        //make linkage map
        LinkedList<Integer>[] link = new LinkedList[N * N];
        for (int i = 0; i < N * N; i++) {
            link[i] = new LinkedList<Integer>();
            if (maze.codePointAt(i) == 'W')
                continue;

            if (i - N >= 0 && maze.codePointAt(i - N) != 'W')
                link[i].add(i - N);

            if (i / N == (i - 1) / N && i - 1 >= 0 && maze.codePointAt(i - 1) != 'W')
                link[i].add(i - 1);

            if (i / N == (i + 1) / N && maze.codePointAt(i + 1) != 'W')
                link[i].add(i + 1);

            if (i + N < N * N && maze.codePointAt(i + N) != 'W')
                link[i].add(i + N);
        }

        //distance map initialization
        int[] distances = IntStream.generate(() -> N * N).limit(N * N).toArray();

        getDistance(link, distances, 0, N * N - 1);

        return distances[N * N - 1] == N * N ? -1 : distances[N * N - 1];
    }

    private static void getDistance(LinkedList<Integer>[] link, int[] distances, int start, int dest) {
        LinkedList<int[]> queue = new LinkedList<int[]>();
        int next = start;
        distances[start] = 0;

        while (!link[start].isEmpty()) {
            next = link[start].poll();
            if (distances[start] + 1 < distances[next]) {
                distances[next] = distances[start] + 1;
            }
            queue.add(new int[] { start, next });
        }

        while (!queue.isEmpty()) {
            int[] item = queue.poll();

            while (!link[item[1]].isEmpty()) {
                next = link[item[1]].poll();
                if (distances[item[1]] + 1 < distances[next]) {
                    distances[next] = distances[item[1]] + 1;
                }
                queue.add(new int[] { item[1], next });
            }
        }
    }
}

 

Best Practice

BP는 재귀함수를 이용했습니다. 재귀함수 goTo(int i, int j, int step)는 현재의 위치와 현재위치에 도달하기 위해 움직인 횟수를 가지고 있습니다. 종료 조건에서 invalid한 좌표를 제거하고, graph[i][j] <= step를 이용해 다익스트라 알고리즘과 유사하게 동작하도록 구현했습니다. 코드가 간단해서 좋네요.

public class Finder {
    private final static int INF = Integer.MAX_VALUE;
    private static int[][] graph;

    public static int pathFinder(String maze) {
        initGraph(maze);
        goTo(0, 0, 0);
        return (graph[graph.length - 1][graph.length - 1] == INF) ? -1 : graph[graph.length - 1][graph.length - 1];
    }

    private static void initGraph(String maze){
        String[] lines = maze.split("\n");
        graph = new int[lines.length][lines.length];
        for(int i=0; i<lines.length; i++)
            for(int j=0; j<lines.length; j++)
                graph[i][j] = (lines[i].charAt(j)=='W')?-1:INF;
    }

    private static void goTo(int i, int j, int step){
        if(i==-1 || i==graph.length || j==-1 || j==graph.length || graph[i][j] <= step)
            return;
        graph[i][j] = step;
        goTo(i, j-1, step+1);
        goTo(i, j+1, step+1);
        goTo(i+1, j, step+1);
        goTo(i-1, j, step+1);
    }
}