(Rust) - LeetCode (Medium) : 1391. Check if There is a Valid Path in a Grid

https://leetcode.com/problems/check-if-there-is-a-valid-path-in-a-grid

Check if There is a Valid Path in a Grid - LeetCode

기존의 단순 bfs가 아닌 한 그리드 칸에 두 상태가 섞인 것을 어떻게 표현하는지의 구현도 포함된 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

📑 mask 함수 구현

각 그리드는 숫자 하나로 구성되어 있으므로 6가지 유형에 대해 서로 연결되었는지 판단하기 위해서는 bit masking이 제일 간단해 보입니다. 왜냐하면 여러 상태를 or 연산으로 집합형태의 masking으로 표현 가능하기 때문입니다. match 패턴으로 유형별 or연산을 해서 상태를 나타낼 mask함수를 선언 및 구현해줍니다.

 

📑 순회할 방향 정의

길이 뚫려있는지 확인하기 위한 dirs 배열을 정의해줍니다. 예를 들어 행,열 좌표가 -1, 0 방향이면 위로 향하는 것이므로 현재 방향은 위, 그 반대 방향은 아래가 됩니다. -1, 0으로 가기 위해서는 masking된 그리드 값과 & 연산을 했을 때 0이아니라면 그 길이 뚫려있다고 볼 수 있으므로 확인을 위해 현재 방향과 반대방향을 dir의 원소로 추가해줍니다. 즉, dir의 하나의 좌표를 (행, 열, 현재 방향, 반대 방향) 의 tuple로 정의할 수 있습니다.

 

📑 행, 열, VecDeque, visited 배열 선언

순회를 위한 자료구조들을 선언해줍니다.

📔 풀이과정

📑 사전 작업
1. 첫 순회를 위해 visited[0][0]는 true로, VecDeque인 q의 첫 원소로 0usize, 0usize를 push_back해줍니다.

2. q.pop_front()했을 때 Some인 동안 while loop를 수행하며 bfs를 수행합니다.

  2-1. 뽑았을 때 도착 지점이라면 true를 바로 반환합니다.

  2-3. 다음 방향으로 갈 수 있는지 dirs의 원소를 순회하며 조건을 검사하며 맞다면 q에 다음 좌표를 push_back합니다. 이미 방문했거나 그리드를 벗어났으면 continue해줍니다. 그 외 다음 좌표가 길이 뚫려있다면 push_back합니다.

 

📑 시간 복잡도

O(행 수 * 열 수): 각 칸별 4방향 순회

📑 공간 복잡도

O(행 수 * 열 수): 각 칸 방문

📔 정답 출력 | 반환

우측 아래의 좌표로 도달했다면 true, bfs완료 후에도 도달 못했다면 false를 반환합니다.

---

📕 Code

📔 Rust

use std::collections::VecDeque;

impl Solution {
    const U: i32 = 1;
    const R: i32 = 2;
    const D: i32 = 4;
    const L: i32 = 8;

    fn mask(x: i32) -> i32 {
        match x {
            1 => Self::L | Self::R,
            2 => Self::U | Self::D,
            3 => Self::L | Self::D,
            4 => Self::R | Self::D,
            5 => Self::L | Self::U,
            6 => Self::R | Self::U,
            _ => 0,
        }
    }

    pub fn has_valid_path(grid: Vec<Vec<i32>>) -> bool {
        let r_len = grid.len();
        let c_len = grid[0].len();

        // (행, 열, 현재 방향, 반대 방향)
        let dirs = [
            (-1, 0, Self::U, Self::D),
            (0, 1, Self::R, Self::L),
            (1, 0, Self::D, Self::U),
            (0, -1, Self::L, Self::R),
        ];

        let mut visited = vec![vec![false; c_len]; r_len];
        visited[0][0] = true;

        let mut q = VecDeque::new();
        q.push_back((0usize, 0usize));

        while let Some((r, c)) = q.pop_front() {
            if r == r_len - 1 && c == c_len - 1 {
                return true;
            }

            for &(dr, dc, cur_dir, opp_dir) in &dirs {
                let nr = r as i32 + dr;
                let nc = c as i32 + dc;

                if nr < 0 || nr >= r_len as i32 || nc < 0 || nc >= c_len as i32 {
                    continue;
                }
                let nr = nr as usize;
                let nc = nc as usize;

                if visited[nr][nc] {
                    continue;
                };

                if Self::mask(grid[r][c]) & cur_dir != 0 && Self::mask(grid[nr][nc]) & opp_dir != 0
                {
                    visited[nr][nc] = true;
                    q.push_back((nr, nc));
                }
            }
        }

        false
    }
}

 

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.