LeetCode - Shortest Path in Binary Matrix

문제

💡 n x n인 이차원 배열인 그리드가 주어졌을 때, 출발지에서 목적지까지 도착하는 가장 빠른 경로의 길이를 반환하시오. 만약 경로가 없다면 -1을 반환하시오.

출발지 : top-left
목적지 : bottom -right

예시

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1

제약 조건

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

문제 링크 -> https://leetcode.com/problems/shortest-path-in-binary-matrix/

풀이

문제 이해하기

• 값이 0인 셀만 지나갈 수 있다.
• 셀은 8가지 방향으로 연결되어 있다. (edge와 corner 방향으로 총 8가지다).
• 연결된 셀을 통해서만 지나갈 수 있다.
• 경로가 없다면 -1을 반환한다.
• 출발지나 목적지의 값이 0이 아니면 -1을 반환한다.
• 그리드의 셀 갯수가 시간복잡도를 결정한다.

접근 방법 생각하기

• bfs를 사용하면 출발지에서 가까운 순서대로 탐색할 수 있다.
• 출발지에서 가까운 순서대로 탐색하다가 목적지에 도착하면 거리를 반환한다.

코드 설계

• 출발지나 목적지의 값이 0이 아니면 -1을 반환한다.
• bfs로 그리드를 탐색한다.
• 8가지 방향으로 탐색한다. 아직 방문하지 않았고 셀의 값이 0인 경우 셀을 방문할 수 있다.
• 방문 가능한 셀들을 큐에 추가하고 이동 거리를 1 증가시킨다.
• 도착지에 도착하면 이동 거리를 반환한다.

코드 구현

public class ShortestPathBinaryMatrix {

    private int[][] grid;
    private boolean[][] visited;

    public int solve(int[][] grid) {
        this.grid = grid;
        this.visited = new boolean[grid.length][grid.length];
        int startingPoint = grid[0][0];
        int endPoint = grid[grid.length - 1][grid.length - 1];

        if (startingPoint != 0 || endPoint != 0) {
            return -1;
        }

        return bfs();
    }

    private int bfs() {
        int result = -1;
        Queue<PathVertex> queue = new ArrayDeque<>();

        queue.offer(new PathVertex(0, 0, 1));
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            PathVertex pathVertex = queue.poll();
            if (isGoal(pathVertex)) {
                result = pathVertex.getPathLength();
                break;
            }
            queue.addAll(findPath(pathVertex));
        }
        return result;
    }

    private boolean isGoal(PathVertex pathVertex) {
        return pathVertex.getRow() == grid.length - 1 && pathVertex.getColumn() == grid.length - 1;
    }

    private List<PathVertex> findPath(PathVertex pathVertex) {
        List<PathVertex> result = new ArrayList<>();

        for (Directions direction : Directions.values()) {
            int newRow = pathVertex.getRow() + direction.getDirection().getRow();
            int newColumn = pathVertex.getColumn() + direction.getDirection().getColumn();

            if (validCoordinate(newRow, newColumn)) {
                PathVertex newPath = new PathVertex(newRow, newColumn, pathVertex.getPathLength() + 1);
                result.add(newPath);
                visited[newRow][newColumn] = true;
            }
        }

        return result;
    }

    private boolean validCoordinate(int row, int column) {
        return isInBoundary(row, column) && isPath(row, column) && isNotVisited(row, column);
    }

    private boolean isInBoundary(int row, int column) {
        return row >= 0 && column >= 0 && row < grid.length && column < grid.length;
    }

    private boolean isPath(int curRow, int curColumn) {
        return grid[curRow][curColumn] == 0;
    }

    private boolean isNotVisited(int curRow, int curColumn) {
        return !this.visited[curRow][curColumn];
    }
}

public class PathVertex {

    private final int row;
    private final int column;
    private final int pathLength;

    public PathVertex(int row, int column, int pathLength) {
        this.row = row;
        this.column = column;
        this.pathLength = pathLength;
    }

    public int getRow() {
        return row;
    }

    public int getColumn() {
        return column;
    }

    public int getPathLength() {
        return pathLength;
    }
}

public class Direction {
    private final int row;
    private final int column;

    public Direction(int row, int column) {
        this.row = row;
        this.column = column;
    }

    public int getRow() {
        return row;
    }

    public int getColumn() {
        return column;
    }
}

public enum Directions {
    NORTH(new Direction(-1, 0)),
    NORTHEAST(new Direction(-1, 1)),
    EAST(new Direction(0, 1)),
    SOUTHEAST(new Direction(1, 1)),
    SOUTH(new Direction(1, 0)),
    SOUTHWEST(new Direction(1, -1)),
    WEST(new Direction(0, -1)),
    NORTHWEST(new Direction(-1, -1));

    private final Direction direction;

    Directions(Direction direction) {
        this.direction = direction;
    }

    public Direction getDirection() {
        return direction;
    }
}

테스트 코드

class ShortestPathBinaryMatrixTest {

    @Test
    void fail() {
        int[][] grid1 = {
                {1, 0, 0},
                {1, 1, 0},
                {1, 1, 0}
        };

        int[][] grid2 = {
                {0, 0, 0},
                {1, 1, 0},
                {1, 1, 1}
        };

        int[][] grid3 = {
                {0, 0, 0},
                {1, 1, 1},
                {1, 1, 0}
        };


        ShortestPathBinaryMatrix shortestPathBinaryMatrix = new ShortestPathBinaryMatrix();
        int result1 = shortestPathBinaryMatrix.solve(grid1);
        int result2 = shortestPathBinaryMatrix.solve(grid2);
        int result3 = shortestPathBinaryMatrix.solve(grid3);

        Assertions.assertEquals(-1, result1);
        Assertions.assertEquals(-1, result2);
        Assertions.assertEquals(-1, result3);
    }

    @Test
    void solve() {
        int[][] grid1 = {
                {0, 0, 0},
                {1, 1, 0},
                {1, 1, 0}
        };

        int[][] grid2 = {
                {0, 1, 1, 1, 1, 1, 1, 1},
                {0, 1, 1, 0, 0, 0, 0, 0},
                {0, 1, 0, 1, 1, 1, 1, 0},
                {0, 1, 0, 1, 1, 1, 1, 0},
                {0, 1, 1, 0, 0, 1, 1, 0},
                {0, 1, 1, 1, 1, 0, 1, 0},
                {0, 0, 0, 0, 0, 1, 1, 0},
                {1, 1, 1, 1, 1, 1, 1, 0}
        };

        ShortestPathBinaryMatrix shortestPathBinaryMatrix = new ShortestPathBinaryMatrix();
        int result1 = shortestPathBinaryMatrix.solve(grid1);
        int result2 = shortestPathBinaryMatrix.solve(grid2);

        Assertions.assertEquals(4, result1);
        Assertions.assertEquals(25, result2);
    }
}