뒤죽박죽 코딩 이야기

2022년 05월 16일 월요일 - 월요일 시러

오늘 올려볼 문제는 1091번 Shortest Path in Binary Matrix 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

오늘 일하기 넘 시러씀

입력

사진에서도 볼 수 있듯이 2차원 int 배열이 1개가 입력으로 들어온다.

풀이 및 코드

맨 끝부터 끝까지 가장 빠른길로 갔을 때 얼마나 걸리는 지 구하여 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

BFS를 사용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0] != 0) return -1;

        int[] xdir = {1, 0, -1, 1, 0, -1, 1, 0, -1};
        int[] ydir = {1, 1, 1, 0, 0, 0, -1, -1, -1};
        boolean[][] visit = new boolean[grid.length][grid[0].length];

        Queue<point> q = new LinkedList<>();
        q.add(new point(0, 0));

        int result = 0;

        while(!q.isEmpty())
        {
            int size = q.size();

            result++;

            for(int i = 0; i < size; i++)
            {
                point now = q.poll();

                if(visit[now.y][now.x]) continue;

                visit[now.y][now.x] = true;

                if(now.y == grid.length - 1 && now.x == grid[0].length - 1) return result;

                for(int y : ydir)
                {
                    for(int x : xdir)
                    {
                        int tempy = y + now.y;
                        int tempx = x + now.x;

                        if(0 <= tempy && tempy < grid.length)
                            if(0 <= tempx && tempx < grid[0].length)
                                if(grid[tempy][tempx] == 0)
                                    q.add(new point(tempx, tempy));

                    }
                }
            }
        }

        return -1;
    }

    class point{
        int x, y;

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

제출 화면

오늘은 문제가 조금 귀찮아서 푸는데 시간이 좀 걸렸다.

내일은 좀 덜 귀찮으면서 재밌는 문제가 나왔으면 좋겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.