자료구조와 알고리즘_2_오른손 법칙

[ ✔️오른손 법칙 ]

 

📍오른손 법칙이란? :

"우수법" 이라고 불리기도 한다.

오른손으로 벽을 짚으면서 앞으로 나아간다는 의미

어떤 미로에서든 통용되는 방법은 아니지만, 탈출로가 있다는게 보장된다면 어느 정도 효과 있는 방법이다.

 

📍구현법_이론 :

case1) 현재 바라보는 방향을 기준으로 오른쪽으로 갈 수 있는가?
	: 오른쪽 방향으로 90도 회전 -> 앞으로 한 보 전진
    
case2) 현재 바라보는 방향을 기준으로 전진할 수 있는가?
	: 앞으로 한 보 전진
    
case3) 위의 두 경우 모두 불가능한 경우 
	: 왼쪽 방향으로 90도 회전

 

 

방향값은 열거형으로 선언하여 int 값으로 표현 할 수 있도록 함

enum Dir	// 반시계 방향
{
    DIR_UP = 0,
    DIR_LEFT = 1,
    DIR_DOWN = 2,
    DIR_RIGHT = 3,
    DIR_COUNT = 4,
};

 

📍방향 전환 계산법_1 :

방향 전환을 하는 경우 switch-case 문으로 모든 케이스에대한 분기를 만들어 방향전환을 해줄 수 있다.

// _dir : 현재방향
switch (_dir)
{
case DIR_UP:
    _dir = DIR_LEFT;
    break;
case DIR_LEFT:
    _dir = DIR_DOWN;
    break;
case DIR_DOWN:
    _dir = DIR_RIGHT;
    break;
case DIR_RIGHT:
    _dir = DIR_UP;
    break;
}

하지만 이와 같이 구현하면 모든 경우에 대한 case문을 다 작성해줘야하는 불편함이 있다.

이동 가능 방향이 대각선도 추가되어 8방향이 되면 case문은 8개로 늘어나게된다.  (능률 ↓)

 

📍방향 전환 계산법_2 : 

방향(Dir)을 열거형으로 선언해줬기에 정수값으로 표현가능하다.

이 점을 활용하여 공식을 만들 수 있다.

방향 값이 "반시계순(up →  left → down → right)" 으로 선언되어 있기에, 우측 회전의 경우 "현재 방향(_dir) - 1" 연산을, 좌측의 경우 "_dir + 1" 연산을 해주면 된다.

// 우측 90˚회전 공식
newDir = (_dir - 1 + DIR_COUNT) % DIR_COUNT;

// 좌측 90˚회전 공식
newDir = (_dir + 1) % DIR_COUNT;

 

 

📍Forward 방향으로 진행 가능여부 체크하는 법 : 

Forward 방향은 현재 바라보고 있는 방향을 의미한다. 즉, 진행 예정인 곳이다.

진행 예정인 곳의 TILE 타입이 EMPTY 면 진행 가능하고, WALL이면 불가능하다.

// 선언부
bool	CanGo(Pos pos);

// 정의부
bool Player::CanGo(Pos pos)
{
    TileType tileType = _board->GetTileType(pos);
    return tileType == TileType::EMPTY;
}

// TileType : EMPTY, WALL

진행 예정인 곳의 좌표를 구하는 방법은 switch-case문으로도 만들 수 있지만 Pos 배열을 만들면 더 간단하게 구현가능하다.

 

각 방향으로 이동시 이동 값을 배열의 원소로 넣어주고, 인덱스는 열거형으로 만들어준 방향값에 맞춰준다.

Pos front[4] =
{
    // y, x
    Pos{-1,  0 },	// UP
    Pos{ 0, -1 },	// LEFT
    Pos{ 1,  0 },	// DOWN
    Pos{ 0,  1 },	// RIGHT
};

newPos = pos + front[dir]
// pos : 현재좌표 , dir : 진행방향

 

📍결과 : 

 

📍장단점 : 

장점 : 

비교적 간단하게 구현할 수 있다.

 

단점 : 

길찾기 알고리즘으로 사용하기 힘들정도로 불필요한 길을 전부 체크하면서 가고 있다.

최적화된 최단거리를 찾아주는 방법은 아니다.

 

---

Next Note

자료구조와 알고리즘_3