[C#] 1091. Shortest Path in Binary Matrix

1. 문제

 

n x n 크기의 이진 행렬이 주어진다.

가장 짧은 clear path의 길이를 리턴하면 된다.

clear path가 없다면 -1을 리턴한다.

 

clear path는 이진 행렬의 왼쪽 위(0, 0)에서부터 시작해서 오른쪽 아래(n - 1, n - 1)까지의 경로이다.

- 방문한 길의 모든 셀은 0이다.

- 경로의 인접한 모든 셀은 8방향으로 연결되어 있다. (즉, 서로 다르며 모서리를 공유한다.)

 

clear path의 길이는 방문한 셀의 갯수이다.

 

 

---

 

2. 풀이 과정

 

BFS (Breath First Search)를 사용하여 최단 경로를 구한다.

너비 우선 탐색으로 넓게 cell을 방문하면서 방문하기 전에 어느 cell에서 출발했는지 기록하고, 목적지에 도착하면 출발했던 cell을 역순으로 찾아가며 최단 거리를 출력하면 된다.

 

visited 딕셔너리는 해당 cell의 방문여부와 방문했다면 어디서 방문했는지 기록하는 용도이다.

queue는 다음과 같은 순서로 사용한다.

1. 최초 cell의 좌표 enqueue

2. dequeue 한 번 실행.

3. 2에서 얻은 cell의 좌표로부터 방문할 수 있으면서 이전에 방문하지 않았던 cell들을 모두 enqueue.

4. queue의 Count가 0이 될 때까지 2~3 반복.

 

queue가 완전히 비었다면 목적지 좌표로부터 visited를 사용하여 역순으로 올라가며 거리를 기록.

 

출발지점에 도착하였다면 결과를 return.

 

첫 cell의 값이 1이라면 탐색할 필요가 없으므로 바로 -1을 return.

 

마지막 cell의 좌표가 visited에 없다면 목적지에 도착하지 못한 것이므로 -1을 return.

 

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

        var queue = new Queue<(int, int)>();
        var visited = new Dictionary<(int, int), (int, int)>();
        var n = grid.Length;

        queue.Enqueue((0, 0));
        visited.Add((0, 0), (-1, -1));

        while (queue.Count() > 0)
        {
            var curCell = queue.Dequeue();
            int x = curCell.Item1;
            int y = curCell.Item2;

            for (int i = -1; i < 2; ++i)
            {
                for (int j = -1; j < 2; ++j)
                {
                    if (x + i >= 0 && y + j >= 0 && x + i < n && y + j < n)
                    {
                        if (grid[x + i][y + j] == 0 && visited.TryAdd((x + i, y + j), (x, y)))
                        {
                            queue.Enqueue((x + i, y + j));
                        }
                    }
                }
            }
        }

        var result = -1;

        if(visited.ContainsKey((n - 1, n - 1)))
        {
            result = 0;
            int x = n - 1;
            int y = n - 1;

            while(x != -1 && y != -1)
            {
                var cell = visited[(x, y)];
                x = cell.Item1;
                y = cell.Item2;
                result++;
            }
        }

        return result;
    }
}