[백준] 2178번 미로찾기(C#)

문제

코드

using System;
using System.Text;
using System.Collections.Generic;

namespace dongsik
{
    class Algorithm
    {
        static int n, m; // n * m 
        static int[,] map; // 지도
        static int[,] dist; // 거리
        static bool[,] visited; // 방문처리
        static int[] dx = {-1, 0, 1, 0}; // x좌표 이동
        static int[] dy = {0, -1, 0, 1}; // y좌표 이동
        
        private static void BFS(int x, int y)
        {
            Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>(); // queue
            queue.Enqueue(new Tuple<int, int>(x, y)); // queue에 (x, y)를 담음
            visited[x, y] = true; // 방문처리
            
            while(queue.Count > 0) // queue에 아무것도 없으면 끝내야 함
            {
                Tuple<int, int> current = queue.Dequeue(); // queue에서 꺼냄(선입선출)
                for(int i = 0; i < 4; i++)
                {
                    int nx = current.Item1 + dx[i]; // x만큼 이동
                    int ny = current.Item2 + dy[i]; // y만큼 이동
                    // (-1, 0), (0, -1), (1, 0), (0, 1) 총 4가지 방향으로 이동 할 것임
                    
                    if(nx < 0 || ny < 0 || nx >= n || ny >= m) { continue; } // 만약 이동한 범위가 map을 벗어난다면 continue
                    if(visited[nx, ny] || map[nx, ny] == 0) { continue; } // 만약 방문했거나 갈 수 없는 위치라면 continue
                    
                    queue.Enqueue(new Tuple<int, int>(nx, ny)); // 만약 들릴 수 있는 방향이라면 q에 삽입
                    dist[nx, ny] = dist[current.Item1, current.Item2] + 1; // 거리를 직전 거리에 +1을 해줘서 업데이트
                    visited[nx, ny] = true; // 방문처리
                }
            }
        }
        
        static void Main(string[] str)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            n = input[0];
            m = input[1];

            map = new int[n, m];
            dist = new int[n, m];
            visited = new bool[n, m];
            
            // 행
            for(int i = 0; i < n; i++)
            {
                string input2 = Console.ReadLine();
                // 열
                for(int j = 0; j< m; j++)
                {
                    map[i, j] = input2[j] - '0';
                }
            }
            
            BFS(0, 0);
            Console.WriteLine(dist[n-1, m-1] + 1);
        }
        
    }
}

고민

map에서 상하좌우를 어떻게 움직일지 고민했다. 다른 분들이 dx, dy를 만들어 좌표의 이동값을 만들어두셨다.

static int[] dx = { -1, 0, 1, 0 }; 이렇게. 이러면 dx[0]이면 x값 -1로 움직이고 dx[2]면 x값을 1움직인다.

 

그리고 dist[n-1, m-1]에 왜 +1을 해주는지도 몰랐는데, 검색해보니 BFS 알고리즘은 시작점을 0으로 보고 거리를 계산하기 때문에 첫 dist는 1이 아니라 0이 저장이 되어있을 겁니다. 그래서 +1을 해줘야 올바른 거리를 계산할 수 있었다. 만약 +1을 해주기 싫으면 bfs가 시작되는 곳 visited = true를 해주는 곳에 dist = 1을 해주면 된다.