[ BOJ/C# ] 14940 쉬운 최단거리

https://www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

BFS 문제이다. 다른 문제와 차별점이 있다면 목표 지점부터의 거리를 계산하여 출력하는 것이다. 

비슷하지만 이런 차별점이 BFS의 재미인 듯하다🤭🤭

using System;
using System.IO;
using System.Text;

namespace B14940
{
    class Program
    {
        static int N, M;
        static int[,] map = new int[1001, 1001];
        static bool[,] visited = new bool[1001, 1001];
        static Queue<(int, int)> q0 = new Queue<(int, int)>();
        static Queue<(int, int)> q1 = new Queue<(int, int)>();
        static int[] dx = { -1, 1, 0, 0 };
        static int[] dy = { 0, 0, -1, 1 };
        static int index = 0;
        static void BFS()
        {
            //갈 수 있는 모든 맵을 확인하기
            while (q0.Count > 0 || q1.Count > 0)
            {
                if (q0.Count > 0)
                {
                    while (q0.Count > 0)
                    {
                        var deq = q0.Dequeue();
                        int deqx = deq.Item1;
                        int deqy = deq.Item2;
                        visited[deqx, deqy] = true;
                        //4방향 확인
                        for (int i = 0; i < 4; i++)
                        {
                            deqx = deq.Item1 + dx[i];
                            deqy = deq.Item2 + dy[i];
                            //맵을 벗어나거나 이미 방문했으면 continue
                            if (deqx < 0 || deqy < 0 || deqx >= N || deqy >= M || visited[deqx, deqy] == true)
                                continue;
                            //갈 수 있다면 다음 Queue에 넘기고 걸음 수 더해주기
                            if (map[deqx, deqy] == 1)
                            {
                                q1.Enqueue((deqx, deqy));
                                map[deqx, deqy] += index;
                            }
                            visited[deqx, deqy] = true;
                        }
                    }
                }
                else if (q1.Count > 0)
                {
                    while(q1.Count > 0)
                    {
                        var deq = q1.Dequeue();
                        int deqx = deq.Item1;
                        int deqy = deq.Item2;
                        visited[deqx, deqy] = true;
                        //4방향 확인
                        for (int i = 0; i < 4; i++)
                        {
                            deqx = deq.Item1 + dx[i];
                            deqy = deq.Item2 + dy[i];
                            //맵을 벗어나거나 이미 방문했으면 continue
                            if (deqx < 0 || deqy < 0 || deqx >= N || deqy >= M || visited[deqx, deqy] == true)
                                continue;
                            //갈 수 있다면 다음 Queue에 넘기고 걸음 수 더해주기
                            if (map[deqx, deqy] == 1)
                            {
                                q0.Enqueue((deqx, deqy));
                                map[deqx, deqy] += index;
                            }
                            visited[deqx, deqy] = true;
                        }
                    }
                }
                index++;
            }
        }
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();

            int[] nm = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
            N = nm[0];
            M = nm[1];
            int x = 0;
            int y = 0;
            for(int i = 0; i < N; i++)
            {
                int[] input = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
                for (int j = 0; j < M; j++) //맵 입력
                {
                    map[i, j] = input[j];
                    if (input[j] == 2)  //시작 좌표
                    {
                        x = i;
                        y = j;
                        map[x, y] = 0;
                    }
                }
            }
            q0.Enqueue((x, y));
            BFS();
            //출력
            for(int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    //방문하지 못하고 원래 갈 수 없는 0이 아니라면 -1출력
                    if (!visited[i, j] && map[i, j] != 0) map[i, j] = -1;
                    sb.Append(map[i, j]);
                    if (j < M - 1) sb.Append(" ");
                }
                sb.Append("\n");
            }
            sw.Write(sb);
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}