[코딩테스트 일지 - 99클럽] 6일차 - 게임 맵 최단거리
코딩 테스트 준비 일지 6 일차
문제 설명
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
S X O O O
O X O X O
O X O O O
O O O X O
X X X X D
S : 시작지점
D : 도착지점
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.
R X O O O
R X O X O
R X R R R
R R R X R
X X X X R
R : 이동한 경로
두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.
R X R R R
R X R X R
R X R O R
R R R X R
X X X X R
R : 이동한 경로
위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
S X O O O
O X O X O
O X O O O
O O O X X
X X X X R
만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
제한사항
maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
입출력 예
maps answer
[[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]]
11
[[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]]
-1
문제 풀이 접근
이런 문제는 최단거리 경로 탐색할 때, 아주 잘나오는 문제다.
맵을 먼저 주고, 여기서 최단거리 경로를 탐색하라라는 것이다.
나는 이 문제에서 아쉽게도 DFS 개념을 먼저 떠올려서 58분 정도에 DFS 개념을 활용하여 TC를 모두 패스했는데, 효율성 TC가 모두 실패했다.
도저히 DFS로는 효율성 TC를 패스할 방법이 생각나지 않아, 방법론의 문제라고 생각하고 다른 사람들의 풀이를 참고했다.
역시나 BFS로 푸는게 정답이었고, Depth 기반으로 찾는 DFS는 경로를 앞에서 찾던 뒤에서 찾던 결국 마지막의 경로 Value를 비교하기 전까지는 최단거리인지 알 수 없다.
단, BFS는 다르다. Breath First 이기 때문에 인접한 노드 ( 트리 상 가로 축 으로 생각하면 편하다 ) 를 탐색하여 가장 먼저 끝나는게 결국 최단거리다. 이래서 최단거리 보장이 되는 것.
이런 문제는 플로우가 간단하긴한데 참고할 static 변수들이 조금 있는편이다..
map 의 X, Y 축으로 이동할 맥스 값을 찾는다. 5x5 배열이라면 좌상을 0,0 기준 시 4
방문했는지 체크를 위한 변수를 map 변수와 동일하게 넣는다.
map 과 현재 위치값, 이동해서 넘어온 카운트 값 등등을 갱신하면서 이동한다.
이동할때는 visit 변수의 값이 true 가 되었는지, direction 을 통해 0 보다 작게, Max 보다 크게 맵밖으로 나갔는지 체크해서 이동할 수 있는지 여부를 확인하면서 이동한다.
목적지에 도착했을 경우, 이동한 값이 최단거리라고 판단될 때 이동 값을 갱신한다.
작성 코드 ( C# ) - 효율성 실패 DFS 코드
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 > count)
result = count;
return;
}
isVisited[x, y] = true;
for(int i = 0; i < 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) && (GoalPos[1] == y);
}
public static bool CheckMovablesDirection(ref int[,] maps, int x, int y)
{
if ((limitXPos <= x) || (0 > x) || (limitYPos <= y) || (0 > y))
return false; // 맵 외부에 나가는 케이스는 모두 False;
if (maps[x, y] != 1)
return false; // 맵이 아니어도 False
return true;
}
}코드 결과 - 효율성 실패
문제 풀이 접근2
다시 효율성 테스트를 통과하기 위해 BFS를 사용할 수도 있으나, 이동거리 전부를 Map에 기록하는 방식을 이전에 공부한 적이 있다. 어느 한 지점에서 B 지점으로 이동할때 까지의 거리 값을 모두 2차원 배열에 입력해서 기억하도록 하는 방식이다.
정답 작성 코드 ( C# )
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<(int, int)> q = new Queue<(int, int)> ();
q.Enqueue((0, 0));
while(q.Count > 0)
{
var curPos = q.Dequeue();
if(curPos.Item1 == GoalPos[0] && curPos.Item2 == GoalPos[1])
{
result = map[curPos.Item1, curPos.Item2];
return;
}
for(int i = 0; i < 4; ++i)
{
int NextPosX = (curPos.Item1 + dx[i]);
int NextPosY = (curPos.Item2 + dy[i]);
if ((NextPosX >= map.GetLength(0)) || (NextPosX < 0) || (NextPosY >= map.GetLength(1) || (NextPosY < 0)))
continue;
if (map[NextPosX, NextPosY] != 1) continue;
q.Enqueue((NextPosX, NextPosY));
map[NextPosX, NextPosY] = (map[curPos.Item1, curPos.Item2] +1);
}
}
return;
}
}
}
코드 결과
