임의의 시작점에서 정해진 목적지의 출구(Exit)까지 PathWay가 있는지 도출할 수 있을까?
최근 알고리즘 공부를 다시 시작하면서 재귀함수적 사고에 익숙해지려고 연습중에 있다. 이런 이론적인 측면도 공부를 해야 좀 더 다양한 사고가 가능한 것 같다. 실무에 쓰이기는 어려움이 있을 것 같은데 일단 구현력을 갖춘 뒤 선택적 사용을 할 수 있는 것과 전혀 고려 대상이 아닌 것은 확실히 다른 것 같다.
미로찾기는 시작점에서 도착점까지 갈 수 있는지 그리고 그 Pathway는 어떻게 되는지 도출하는 문제이다. 재귀에서 너무 유명한 문제라 풀이 방식이 많지만 최근 회사에서 주로 사용하는 C#으로 풀어보았다.
🎉Recursion
재귀
임의의 시작점에서 (x,y) 출발을 한다 가정했을 때, 임의의 시작점이 Wall이라면 더 이상 볼 것도 없이 출구를 찾지 못하는 경우 일 것이다. 또한 이 점이 미로의 범위를 벗어난 경우(예를들어 x=-100)인 경우도 실패이다. 만약 해당 위치가 출구라면 True를 반환하면 될것이다.
이외에 어느것도 해당하지 않는다면 해당 위치 기준 동서남북으로 이동한뒤 (벽이나 지나간 위치가 아니라면) 다시 동일한 작업을 반복한다. 이중 True를 반환한다면 출구를 찾는 경우가 도출된다.
여기서 하나 생각해야할 점이 있는데, Pathway가 지나간 경로 중 막혀있는 길은 막혀있다는 표시를 해주도록 해준다.
이를 상수로 표현하면
private const int PATHWAY_COLOUR = 0; //통행가능
private const int WALL_COLOUR = 1; //벽
private const int BLOCKED_COLOUR = 2; //갈수있지만 막혀있음
private const int PATH_COLOUR = 3; //지나간곳
이렇게 표시해주도록 해준다. 이를 코드로 표현하면.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Simulation
{
class Program
{
private static int N = 8;
private static int[,] maze = new int[8, 8]{
{ 0,0,0,0,0,0,0,1 },
{ 0,1,1,0,1,1,0,1 },
{ 0,0,0,1,0,0,0,1 },
{ 0,1,0,0,1,1,0,0 },
{ 0,1,1,1,0,0,1,1 },
{ 0,1,0,0,0,1,0,1 },
{ 0,0,0,1,0,0,0,1 },
{ 0,1,1,1,0,1,0,0 }
};
private const int PATHWAY_COLOUR = 0; //통행가능
private const int WALL_COLOUR = 1; //벽
private const int BLOCKED_COLOUR = 2; //갈수있지만 막혀있음
private const int PATH_COLOUR = 3; //지나간곳
public static bool FindMazePath(int x, int y)
{
//미로 범위 벗어남
if (x < 0 || y < 0 || x >= N || y >= N)
{
return false;
}
//길이 아닌경우
else if (maze[x, y] != PATHWAY_COLOUR)
{
return false;
}
//도착함
else if (x == N - 1 && y == N - 1)
{
maze[x, y] = PATH_COLOUR;
return true;
}
//그외경우
else
{
//일단 지나간 길 표시
maze[x, y] = PATH_COLOUR;
//동서남북 재귀해서 길이 있다면
if (FindMazePath(x - 1, y) || FindMazePath(x, y + 1)
|| FindMazePath(x + 1, y) || FindMazePath(x, y - 1))
{
return true;
}
//길이 없는 곳이다
maze[x, y] = BLOCKED_COLOUR; //dead End
return false;
}
}
public static void printMaze()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
Console.Write(maze[i, j]);
}
Console.WriteLine();
}
}
public static void Main(string[] args)
{
printMaze();
Console.WriteLine(FindMazePath(0, 0));
Console.WriteLine();
printMaze();
}
}
}
막히지 않은(2) 경로 최종 결과값 (3)으로 된 Root를 확인할 수 있다.
반응형
'Algorithms' 카테고리의 다른 글
[Recursion:Backtracking, 깊이우선 탐색 예제] N-Queen C# (0) | 2021.03.09 |
---|---|
[Bakjoon/2577번] 숫자의 개수[Java] (1) | 2019.11.27 |