[Graphs] Graphs-BFS- Shortest path

한달째 Tree 랑 Graph 짬짬이 공부중인데 양도 많고 그만큼 중요하단 뜻이겟지.

---

graph문제에서 DFS를 쓰는 BFS를 쓰든 상관없지만 확실이 Shortest path문제에서는 BFS를 쓰는것이 좋다고한다.

방대한 Grid맵에서 목적지까지 가장 단기간의 경로를 찾는 경우를 생각해봤을때에 DFS를 쓰면 모든 맵 구석구석을 먼저 뒤지게될테니 불필요하니 로봇으로 부터 가까운곳부터 경로를 뒤지는 DFS가 효과적이다.

 

https://leetcode.com/problems/shortest-path-in-binary-matrix/

Shortest Path in Binary Matrix - LeetCode

드디어 말로만듣던 최단거리 문제를...

 

• TC: O(n^2)

class Solution {
public:
    vector<vector<int>> grid;
    vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
    int n;
    
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if (grid[0][0] == 1) {
            return -1;
        }
        
        this->grid = grid;
        n = int(grid.size());
        vector<vector<bool>> seen(n, vector<bool>(n, false));
        queue<vector<int>> queue;
        seen[0][0] = true;
        queue.push({0, 0, 1}); // row, col, steps
        
        while (!queue.empty()) {
            vector<int> curr = queue.front();
            queue.pop();
            int row = curr[0], col = curr[1], steps = curr[2];
            if (row == n - 1 && col == n - 1) {
                return steps;
            }
            
            for (vector<int>& direction: directions) {
                int nextRow = row + direction[0], nextCol = col + direction[1];
                if (valid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
                    seen[nextRow][nextCol] = true;
                    queue.push({nextRow, nextCol, steps + 1});
                }
            }
        }
        
        return -1;
    }
    
    bool valid(int row, int col) {
        return 0 <= row && row < n && 0 <= col && col < n && grid[row][col] == 0;
    }
};

 

와 chatGPT 미쳤어.. 코드한줄한줄을 다 설명해버리네. 이렇게 한줄한줄 말하면서 코딩 인터뷰하면 바로 합격일듯... 이걸 잘 활용하면 최고의 학습을 내겠지만 쉽게만 할려고한다면 아무것도 못배우는 코더가 되겠지.

 

Sure! I'd be happy to explain each part of the code in more detail:

1. The directions array: This array stores the 8 possible directions in which a cell can be moved to, which are right, down, down-right, down-left, left, up, up-right, and up-left.
2. The shortestPathBinaryMatrix function: This function is the main function that implements the breadth-first search algorithm to find the shortest path in the binary matrix. It takes in a grid argument which is the binary matrix.
3. The if statement: This checks if the starting cell (0, 0) has a value of 1. If it does, there is no path from the top-left to the bottom-right and -1 is immediately returned.
4. The n variable: This stores the size of the binary matrix, which is equal to the number of rows or columns.
5. The seen array: This is a 2D boolean array that stores whether a cell has been visited or not during the BFS.
6. The queue: This is a queue of type vector<int> that stores the cells to be visited during the BFS. It stores the row, column, and steps required to reach the cell.
7. The queue.push statement: This pushes the starting cell (0, 0) into the queue with the number of steps required to reach it set to 1.
8. The while loop: This loop continues until the queue is empty or the bottom-right cell is reached.
9. The curr variable: This variable stores the current cell being visited, which is the front of the queue.
10. The row, col, and steps variables: These variables store the row, column, and number of steps required to reach the current cell.
11. The if statement inside the while loop: This checks if the current cell is the bottom-right cell. If it is, the number of steps required to reach it is returned.
12. The for loop: This loop visits the neighbors of the current cell in all 8 directions stored in the directions array.
13. The nextRow and nextCol variables: These variables store the row and column of the next cell to be visited, based on the current cell and the direction of movement.
14. The valid function: This function checks if a cell is valid to be visited or not, based on its row and column values and the value of the cell itself. If the cell is valid and has not been visited before, it is added to the queue and the seen array is updated.
15. The final return -1 statement: This statement is executed if the queue is empty and the bottom-right cell has not been reached, which means there is no path from the top-left to the bottom-right and -1 is returned.