[알고리즘] Shortest Path in Binary Matrix

포인트

1. BFS 를 이용하여 2차원 데이터에서 제일 빠른 경로를 찾아주는 알고리즘을 작성합니다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int visited[101][101];

    int bfs(vector<vector<int>> grid)
    {
        int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
        int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
        
        int n = grid.size();
        queue<tuple<int, int, int>> q;
        q.push({0, 0, 1});
        visited[0][0] = 1;

        while (!q.empty())
        {
            int x, y, cnt;
            tie(x, y, cnt) = q.front();
            q.pop();

            if (x == n - 1 && y == n - 1)
            {
                return cnt;
            }

            for (int i = 0; i < 8; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                    continue;

                if (grid[nx][ny] == 0 && visited[nx][ny] == 0)
                {
                    q.push({nx, ny, cnt + 1});
                    visited[nx][ny] = 1;
                }
            }
        }
        return -1;
    }

    int shortestPathBinaryMatrix(vector<vector<int>> &grid)
    {
        if (grid[0][0] == 1 || grid[grid.size() - 1][grid.size() - 1] == 1)
            return -1;

        return bfs(grid)
    }
};

python

class Solution(object):
    
    def bfs(self, grid):
        dx = [1, -1, 0, 0, 1, 1, -1, -1]
        dy = [0, 0, 1, -1, 1, -1, 1, -1]

        n = len(grid)
        visited = [[0]*101 for _ in range(101)]
        q = []
        q.append([0, 0, 1])
        visited[0][0] = 1

        while q:
            x, y, cnt = q.pop(0)

            if x == n-1 and y == n-1:
                return cnt

            for i in range(8):
                nx = x+dx[i]
                ny = y+dy[i]

                if not(0<=nx<n and 0<=ny<n): continue

                if grid[nx][ny] == 0 and visited[nx][ny] == 0 :
                    q.append([nx, ny, cnt+1])
                    visited[nx][ny] = 1

        return -1

    def shortestPathBinaryMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if grid[0][0] == 1:
            return -1
        elif grid[len(grid)-1][len(grid)-1] == 1:
            return -1

        return self.bfs(grid)