<h3>코딩 테스트 준비 일지 6 일차</h3><ul class="tight" data-tight="true"><li><p>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://programmers.co.kr/">프로그래머스</a></p></li><li><p>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/deepest-leaves-sum/description/"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/1844">게임 맵 최단거리</a></p></li><li><p>난이도 : 중</p></li></ul><p></p><h6>문제 설명</h6><p>ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.</p><p>지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.</p><p>S X O O O <br>O X O X O<br>O X O O O<br>O O O X O<br>X X  X X D</p><p>S : 시작지점<br>D : 도착지점</p><p>위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.<br>아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.</p><ul class="tight" data-tight="true"><li><p>첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.</p></li></ul><p>R X O O O <br>R X O X O<br>R X R R R<br>R R R X R<br>X X X X R</p><p>R : 이동한 경로</p><ul class="tight" data-tight="true"><li><p>두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.</p></li></ul><p>R X R R R <br>R X R X R<br>R X R O R<br>R R R X R<br>X X X X R<br>R : 이동한 경로 </p><p>위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.<br><br>S X O O O <br>O X O X O<br>O X O O O<br>O O O X X<br>X X  X X R</p><p>만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.</p><p>게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 <strong>최솟값</strong>을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.</p><h5>제한사항</h5><ul class="tight" data-tight="true"><li><p>maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.</p><ul class="tight" data-tight="true"><li><p>n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.</p></li></ul></li><li><p>maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.</p></li><li><p>처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.</p></li></ul><hr><h5>입출력 예</h5><p>maps answer </p><p>[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] </p><p>11 </p><p>[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]</p><p> -1</p><h3>문제 풀이 접근</h3><p>이런 문제는 최단거리 경로 탐색할 때, 아주 잘나오는 문제다. <br>맵을 먼저 주고, 여기서 최단거리 경로를 탐색하라라는 것이다. <br>나는 이 문제에서 아쉽게도 DFS 개념을 먼저 떠올려서 58분 정도에 DFS 개념을 활용하여 TC를 모두 패스했는데, 효율성 TC가 모두 실패했다.</p><p>도저히 DFS로는 효율성 TC를 패스할 방법이 생각나지 않아, 방법론의 문제라고 생각하고 다른 사람들의 풀이를 참고했다. <br>역시나 BFS로 푸는게 정답이었고, Depth 기반으로 찾는 DFS는 경로를 앞에서 찾던 뒤에서 찾던 결국 마지막의 경로 Value를 비교하기 전까지는 최단거리인지 알 수 없다.<br>단, BFS는 다르다. Breath First 이기 때문에 인접한 노드 ( 트리 상 가로 축 으로 생각하면 편하다 ) 를 탐색하여 가장 먼저 끝나는게 결국 최단거리다. 이래서 최단거리 보장이 되는 것.</p><p>이런 문제는 플로우가 간단하긴한데 참고할 static 변수들이 조금 있는편이다..</p><ol class="tight" data-tight="true"><li><p>map 의 X, Y 축으로 이동할 맥스 값을 찾는다. 5x5 배열이라면 좌상을 0,0 기준 시 4</p></li><li><p>방문했는지 체크를 위한 변수를 map 변수와 동일하게 넣는다. </p></li><li><p>map 과 현재 위치값, 이동해서 넘어온 카운트 값 등등을 갱신하면서 이동한다.</p></li><li><p>이동할때는 visit 변수의 값이 true 가 되었는지, direction 을 통해 0 보다 작게, Max 보다 크게 맵밖으로 나갔는지 체크해서 이동할 수 있는지 여부를 확인하면서 이동한다.</p></li><li><p>목적지에 도착했을 경우, 이동한 값이 최단거리라고 판단될 때 이동 값을 갱신한다.</p></li></ol><h3>작성 코드 ( C# ) - 효율성 실패 DFS 코드 </h3><pre spellcheck="false"><code>using System;

class Solution {
    
        static public bool[,] isVisited;
        static public int[] dirYAxis = new int[4] { 0, 0, -1, 1 }; // 
        static public int[] dirXAxis = new int[4] { 1, -1, 0, 0 }; // 
        static public int[] GoalPos;
        static public int limitXPos = 0;
        static public int limitYPos = 0;
        static public int result = 0;
    
    public int solution(int[,] maps) {
            int answer = 0;
            
            limitXPos = maps.GetLength(0); // X 축 맵 길이
            limitYPos = maps.GetLength(1); // Y 축 맵 길이

            isVisited = new bool[limitXPos, limitYPos];

            GoalPos = new int[2] { limitXPos -1, limitYPos -1};
            result = int.MaxValue;
            int[] startPos = { 0, 0 };

            DFS(ref maps, startPos[0], startPos[1], 1);
            if (result == int.MaxValue)
                result = -1;
        
        answer = result;
        return answer;
    }
    
     public static void DFS(ref int[,] maps, int x, int y, int count)
     {
         if (isVisited[x, y] == true)
             return;

         if (CheckGoalPos(x, y) == true)
         {
             if (result &gt; count)
                 result = count;

             return;
         }

         isVisited[x, y] = true;

         for(int i = 0; i &lt; 4; ++i)
         {
             int NextPosX = (x + dirXAxis[i]);
             int NextPosY = (y + dirYAxis[i]);

             if(CheckMovablesDirection(ref maps, NextPosX,NextPosY) == true)
             {
                 DFS(ref maps, NextPosX, NextPosY, count + 1);
             }
             
         }
         isVisited[x, y] = false;
     }

        public static bool CheckGoalPos(int x, int y)
        {
            return (GoalPos[0] == x) &amp;&amp; (GoalPos[1] == y);
        }

        public static bool CheckMovablesDirection(ref int[,] maps, int x, int y)
        {
            if ((limitXPos &lt;= x) || (0 &gt; x) || (limitYPos &lt;= y) || (0 &gt; y))
                return false; // 맵 외부에 나가는 케이스는 모두 False;

            if (maps[x, y] != 1)
                return false; // 맵이 아니어도 False

            return true;
        }
}</code></pre><h3>코드 결과 - 효율성 실패 </h3><img src="https://image.until.blog/sin0105/article/1717243022442" alt="until-392"><h3>문제 풀이 접근2 </h3><p>다시 효율성 테스트를 통과하기 위해 BFS를 사용할 수도 있으나, 이동거리 전부를 Map에 기록하는 방식을 이전에 공부한 적이 있다. 어느 한 지점에서 B 지점으로 이동할때 까지의 거리 값을 모두 2차원 배열에 입력해서 기억하도록 하는 방식이다.</p><h3>정답 작성 코드 ( C# ) </h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;

/*
 * URL : https://school.programmers.co.kr/learn/courses/30/lessons/1844
 */

namespace CodingTestProj
{
    internal class Program
    {
        /*
         * [1,0,1,1,1]
         * [1,0,1,0,1]
         * [1,0,1,1,1]
         * [1,1,1,0,1]
         * [0,0,0,0,1]
         */

        static public bool[,] isVisited;
        static public int[] dx = new int[4] { 0, 0, -1, 1 }; // 
        static public int[] dy = new int[4] { 1, -1, 0, 0 }; // 
        static public int[] GoalPos;
        static public int limitXPos = 0;
        static public int limitYPos = 0;
        static int[,] map;

        static void Main(string[] args)
        {
            //int[,] map = { { 1, 0, 1, 1, 1 }, { 1, 0, 1, 0, 1 }, { 1, 0, 1, 1, 1 }, { 1, 1, 1, 0, 1 }, { 0, 0, 0, 0, 1 } };
            //int[,] map = { { 1, 1, 1, 1, 1 }, { 1, 0, 1, 0, 1 }, { 1, 1, 1, 1, 1 }, { 1, 0, 1, 0, 1 }, { 1, 1, 1, 1, 1 } };

            //TC 3 
            //[[1, 1, 1, 1, 1], [1, 0, 0, 0, 1], [1, 0, 0, 0, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]] 9

            //solution(map);
        }
        static void solution(int[,] maps)
        {
            limitXPos = maps.GetLength(0); // X 축 맵 길이
            limitYPos = maps.GetLength(1); // Y 축 맵 길이

            GoalPos = new int[2] { limitXPos -1, limitYPos -1};
            map = maps;

            int answer = 0;
            BFS(0,0,out answer);
        }

        public static void BFS(int x, int y, out int result)
        {
            result = - 1;
            Queue&lt;(int, int)&gt; q = new Queue&lt;(int, int)&gt; ();
            q.Enqueue((0, 0));

            while(q.Count &gt; 0)
            {
                var curPos = q.Dequeue();

                if(curPos.Item1 == GoalPos[0] &amp;&amp; curPos.Item2 == GoalPos[1])
                {
                    result = map[curPos.Item1, curPos.Item2];
                    return;
                }

                for(int i = 0; i &lt; 4; ++i)
                {
                    int NextPosX = (curPos.Item1 + dx[i]);
                    int NextPosY = (curPos.Item2 + dy[i]);

                    if ((NextPosX &gt;= map.GetLength(0)) || (NextPosX &lt; 0) || (NextPosY &gt;= map.GetLength(1) || (NextPosY &lt; 0)))
                        continue;

                    if (map[NextPosX, NextPosY] != 1) continue;

                    q.Enqueue((NextPosX, NextPosY));
                    map[NextPosX, NextPosY] = (map[curPos.Item1, curPos.Item2] +1);
                }
            }
            return;
        }
    }
}




</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717249089001" alt="until-394"><p></p>

코딩테스트 항해99 클럽 - 6일차