게임 맵 최단거리

문제

• 깊이/너비 우선 탐색 (DFS/BFS) > 게임 맵 최단거리

문제 풀이

using System;
using System.Collections.Generic;

class Solution 
{
    public int solution(int[,] maps) 
    {
        // 행,열
        int rows = maps.GetLength(0);
        int cols = maps.GetLength(1);
        
        // 방향 구하기
        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};
        
        // BFS 큐 및 방문 여부 배열
        bool[,] visited = new bool[rows,cols];
        // 튜플 사용 (x,y,거리가 될거임)
        Queue<(int,int,int)> queue = new Queue<(int,int,int)>();
        
        // 시작위치
        queue.Enqueue((0,0,1));
        visited[0,0] = true;
        
        // 반복문 돌면서 찾기
        while(queue.Count > 0)
        {
            var (x,y,distance) = queue.Dequeue();
            
            // 목표 도착 체크
            if(x == rows - 1 && y == cols - 1)
                return distance;
            
            // 4방향 탐색
            for(int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 내 범위안에 있는지 ?
                // 내가 방문한 적 없는지 ?
                // 내가 갈 수 있는 곳인지 ?
                if(nx >= 0 && nx < rows && ny >= 0 && ny < cols && visited[nx,ny] == false && maps[nx,ny] == 1)
                {
                    visited[nx,ny] = true;
                    queue.Enqueue((nx,ny,distance + 1));
                }
            }
        }
        return -1;
    }

느낀 점

튜플은 처음 사용해보는거라 신기했습니다. A*가 생각나는 문제였습니다.