Path Finder #3: the Alpinist, CodeWars Kata 자바 솔루션

 

Path Finder #3: the Alpinist, CodeWars Kata

사진: 코드워즈

Path Finder #3: the Alpinist

You are at start location [0, 0] in mountain area of NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return minimal number of climb rounds to target location [N-1, N-1]. Number of climb rounds between adjacent locations is defined as difference of location altitudes (ascending or descending).

Location altitude is defined as an integer number (0-9).

 

문제 해설

개행문자로 구분된 N*N의 행렬이 입력값으로 제공됩니다. 행렬은 숫자 0-9로 이루어져 있으며 각 칸의 숫자가 의미하는 것은 높이입니다. 우리는 [0, 0] 위치에서 시작해서 [N-1, N-1]에 도달하는 높이의 변화가 가장 적은 경로를 구해야 합니다. 높이의 변화이란 3 에서 4로 이동할 때 높이가 1 증가하는 것을 의미합니다. 3에서 9로 이동한다면 높이가 6 변화하는 것입니다.

입력값

• String maze: 개행문자로 구분된 0-9로 이루어진 N*N의 행렬

출력값

• int result: [N-1, N-1] 에 도달할 수 있는 가장 적은 높이 변화의 합

 

My Solution

다익스트라 알고리즘으로 풀 수 있는 문제입니다. 먼저 동서남북으로 이동 가능한 경로에서 높이 변화를 거리로 바꾸어 각각 이동 가능한 방향 별로 거리를 계산해 둡니다. 제 경우엔 LinkedList<int[]>[] link에 담았습니다.

그런 다음 다익스트라 알고리즘에서 한 정점으로부터 다른 정점까지의 거리를 계산하기 위한 배열 int[] distances를 생성하고 무한대값(저의 경우는 도달할 수 없을 때의 높이인 N * N * 9를 사용)으로 초기화해줍니다. 이후 우선순위 큐를 이용했습니다.

우선순위 큐 PriorityQueue<int[]> queue는 거리를 기준으로 정렬하여 가장 짧은 거리를 먼저 반환하는 큐입니다. 큐에 시작점을 넣어주고 시작점에서 이동 가능한 가장 짧은 거리의 정점부터 탐색합니다. 다익스트라를 이용해 거리를 지속적으로 업데이트 해주면 최단 거리를 획득할 수 있습니다.

솔루션 코드

테스트 코드

import java.util.*;
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<int[]>[] link = new LinkedList[N * N];
        for (int i = 0; i < N * N; i++) {
            link[i] = new LinkedList<int[]>();
            if (i - N >= 0)
                link[i].add(new int[] { i - N, Math.abs(maze.codePointAt(i - N) - maze.codePointAt(i)) });

            if (i / N == (i - 1) / N && i - 1 >= 0)
                link[i].add(new int[] { i - 1, Math.abs(maze.codePointAt(i - 1) - maze.codePointAt(i)) });

            if (i / N == (i + 1) / N)
                link[i].add(new int[] { i + 1, Math.abs(maze.codePointAt(i + 1) - maze.codePointAt(i)) });

            if (i + N < N * N)
                link[i].add(new int[] { i + N, Math.abs(maze.codePointAt(i + N) - maze.codePointAt(i)) });
        }

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

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

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

    private static void getDistance(LinkedList<int[]>[] link, int[] distances, int start, int dest) {
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[2], o2[2]);
            };
        });

        //add start point
        queue.add(new int[] { start, start, 0 });
        distances[start] = 0;

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

            //avoid rewrite to longer path
            if (distances[item[0]] + item[2] > distances[item[1]]) {
                continue;
            }
            for (int[] v : link[item[1]]) {

                if (distances[item[1]] + v[1] < distances[v[0]]) {
                    distances[v[0]] = distances[item[1]] + v[1];

                    queue.add(new int[] { item[1], v[0], v[1] });
                }
            }
        }
    }
}

 

Best Practice

최단 거리를 구할 때 다익스트라를 이용하는 것은 동일합니다만 객체지향 설계 부분에서 눈여겨 볼만한 BP입니다. 문제에 충실하게 이동가능한 동서남북 경로를 Direction이라는 Enum을 이용해 풀었고요. Position이라는 클래스를 생성해 각각의 정점들을 다뤘습니다. 문제에서 사용하는 용어인 Climb Round를 이용한 int climbRounds(final Position s, final Position t)도 가독성을 높일 수 있는 직관적인 네이밍입니다.

import java.util.Arrays;
import java.util.EnumSet;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Stream;

public class Finder {

    private final int n;
    private final int[][] hills;

    static int pathFinder(final String area) {
        final Finder finder = new Finder(area);
        return finder.climbRounds(new Position(0,0), new Position(finder.n - 1, finder.n - 1));
    }

    public Finder(final String area) {
        n = Math.max(area.indexOf('\n'), 1);
        hills = parse(area);
    }

    private int[][] parse(final String area) {
        final int[][] field = new int[n][n];
        final String[] rows = area.split("\n");
        for (int y = 0; y < n; y++) {
            final String row = rows[y];
            for (int x = 0; x < n; x++) {
                field[y][x] = Character.getNumericValue(row.charAt(x));
            }
        }
        return field;
    }

    int climbRounds(final Position s, final Position t) {
        final int[][] climbRounds = initSquareArea(n, Integer.MAX_VALUE);
        climbRounds[s.y][s.x] = 0;
        final Set<Position> nextVisits = new HashSet<>();
        nextVisits.add(s);
        while (!nextVisits.isEmpty()) {
            final Set<Position> lastVisits = new HashSet<>(nextVisits);
            nextVisits.clear();
            for (final Position source : lastVisits) {
                mooreNeighborsInArea(source).forEach(target -> {
                    final int newTotalClimbRounds = climbRounds[source.y][source.x] + Math.abs(hills[source.y][source.x] - hills[target.y][target.x]);
                    if (newTotalClimbRounds < climbRounds[target.y][target.x]) {
                        climbRounds[target.y][target.x] = newTotalClimbRounds;
                        nextVisits.add(target);
                    }
                });
            }
        }
        return climbRounds[t.y][t.x];
    }

    private static int[][] initSquareArea(final int size, final int value) {
        final int[][] area = new int[size][size];
        for (final int[] row : area) {
            Arrays.fill(row, value);
        }
        return area;
    }

    public Stream<Position> mooreNeighborsInArea(final Position position) {
        return Direction.all().map(position::toDirection).filter(pos -> pos.isInBounds(n, n));
    }

    public enum Direction {

        N(0, -1), E(1, 0), S(0, 1), W(-1, 0);

        private final int dx;
        private final int dy;

        Direction(final int dx, final int dy) {
            this.dx = dx;
            this.dy = dy;
        }

        public Position of(final Position position) {
            return new Position(position.x + dx, position.y + dy);
        }

        public static Stream<Direction> all() {
            return EnumSet.allOf(Direction.class).stream();
        }
    }

    public static class Position {

        public int x;
        public int y;

        public Position(final int x, final int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(final Object o) {
            return this == o || (o instanceof Position && x == ((Position) o).x && y == ((Position) o).y);
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }

        public Position toDirection(final Direction direction) {
            return direction.of(this);
        }

        public boolean isInBounds(final int width, final int height) {
            return x >= 0 && y >= 0 && x < width && y < height;
        }

        @Override
        public String toString() {
            return "[" + x + "," + y + "]";
        }
    }
}