백준 C# - 2178 +) 풀이

최단거리 문제는 BFS를 사용하는 것이 좋다.

101111
101010
101011
111011

먼저 BFS의 최단 경로 과정을 보면 아래와 같이 진행된다. 해당 깊이에 갈 수 있는 주변 칸을 탐색하고 다음 깊이로 넘어가는 것을 확인할 수 있다.

---

BFS가 진행됨에 따라 칸의 값 갱신

BFS를 진행하면서 현재 칸을 방문할때 이전의 방문했던 칸에 1을 더한 값을 현재 셀에 저장하여 몇 번째 방문한 것인지 를 저장하면 마지막 칸에 최단 경로가 저장된다. 

graph[newX, newY] = graph[now.Item1, now.Item2] + 1;

---

BFS 알고리즘 짜기

01 큐 초기화 및 시작 지점 추가하기

Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
// 시작 좌표값 queue에 추가
queue.Enqueue(new Tuple<int,int>(x, y));

---

02 그래프의 값을 갱신하며 최단 거리 구하기

// 큐가 비어있을때까지 반복
while (queue.Count()>0)
{
    // 현재 칸의 좌표 값 추출
    Tuple<int, int> now = queue.Dequeue();
    
    // 상하좌우 검사
    for (int i = 0; i < 4; i++)
    {
        // 새로운 좌표 값 입력
        int newX = now.Item1 + dirX[i];
        int newY = now.Item2 + dirY[i];
        
        // 새로운 좌표 값에 해당되는 graph값이 0이면 무시
        if (graph[newX, newY] == 0 || (newX == 1 && newY == 1))
            continue;
            
        // 새로운 좌표 값에 해당되는 graph값이 1인 경우
        if (graph[newX, newY] == 1)
        {
            // 그래프의 새로운 좌표 값에 현재 칸의 값  + 1 해서 저장
            graph[newX, newY] = graph[now.Item1, now.Item2] + 1;
            // 새로운 죄표값을 큐에 추가
            queue.Enqueue(new Tuple<int, int>(newX, newY));
        }
    }
}

---

코드 전문

using System;
using System.Collections.Generic;
using System.Linq;
namespace baek2
{
    class Program
    {
        static int[,] graph = new int[110, 110];

        static int[] dirX = { 1, -1, 0, 0 };
        static int[] dirY = { 0, 0, 1, -1 };
        public static void BFS(int x, int y)
        {
            Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
            queue.Enqueue(new Tuple<int,int>(x, y));
            while (queue.Count()>0)
            {
                Tuple<int, int> now = queue.Dequeue();
                for (int i = 0; i < 4; i++)
                {
                    int newX = now.Item1 + dirX[i];
                    int newY = now.Item2 + dirY[i];
                    if (graph[newX, newY] == 0 || (newX == 1 && newY == 1))
                        continue;
                    if (graph[newX, newY] == 1)
                    {
                        graph[newX, newY] = graph[now.Item1, now.Item2] + 1;
                        queue.Enqueue(new Tuple<int, int>(newX, newY));
                    }
                }
            }
        }
        public static void Main()
        {

           int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
           int N = input[0];
           int M = input[1];

           for (int i = 1; i <= N; i++)
           {
               string s = Console.ReadLine();
               int index = 1;
               foreach(char c in s)
               {
                   graph[i, index++] = c - '0';
               }
           }
           BFS(1, 1);
           Console.Write(graph[N,M]);
        }
    }
}