JUNGOL/Intermediate_Coder/백트래킹-DFS/1106 : 장기

Intermediate_Coder/백트래킹-DFS/장기

---

문제                                            

N×M장기판에 졸 한개와 말 한개가 놓여 있다. 말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다. 

JUNGOL 백트래킹-DFS 장기

말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자.

 

입력 형식                                     

첫 줄은 장기판 행의 수(N)와 열의 수(M)를 받는다(1≤N, M≤100).

둘째 줄은 말이 있는 위치의 행(R), 열(C)의 수와 졸이 있는 위치의 행(S), 열(K)의 수를 입력받는다.

단, 장기판의 제일 왼쪽 위의 위치가 (1,1)이다. 

각 행과 열은 R(1≤R≤N), C(1≤C≤M), S(1≤S≤N), K(1≤K≤M)이다.

 

출력 형식                                     

말이 졸을 잡기 위한 최소 이동 횟수를 출력한다.

 

입력 예                                        

9 9
3 5 2 8

 

출력 예                                        

2

---

Janggi.h

#include <iostream>

class Janggi : public Base
{
private:
	struct Point
	{
		int x, y;

		bool operator==(const Point& other) const
		{
			return x == other.x && y == other.y;
		}

		friend std::istream& operator>>(std::istream& is, Point& p)
		{
			is >> p.x >> p.y;
			return is;
		}
	};

	int GetLeastMoveCount(int** visited, int n, int m, Point horse, const Point& soldier, int count = 0);
	bool IsOutOfBoard(const Point& p, int n, int m);
};

 

Janggi.cpp

void Janggi::Code()
{
	int n, m;
	std::cin >> n >> m;

	Point horse, soldier;
	std::cin >> horse >> soldier;

	int** visited = new int* [m + 1];
	for (int i = 1; i <= m; i++)
	{
		visited[i] = new int[n + 1];
		for (int j = 1; j <= n; j++)
		{
			visited[i][j] = 999'999'999;
		}
	}

	std::cout << GetLeastMoveCount(visited, n, m, horse, soldier);

	for (int i = 1; i <= m; i++)
	{
		delete[] visited[i];
	}
	delete[] visited;
}

/// <summary>
/// 말이 병사를 잡는 최소 이동 횟수를 반환한다.
/// </summary>
/// <param name="visited">말이 방문한 위치 정보</param>
/// <param name="n">판의 행의 수</param>
/// <param name="m">판의 열의 수</param>
/// <param name="horse">말의 위치</param>
/// <param name="soldier">병사의 위치</param>
/// <param name="count">이동 횟수</param>
/// <returns>최소 이동 횟수</returns>
int Janggi::GetLeastMoveCount(int** visited, int n, int m, Point horse, const Point& soldier, int count)
{
	static int xMoveDir[8]{ -2, -1, 1, 2, 2, 1, -1, -2 };
	static int yMoveDir[8]{ -1, -2, -2, -1, 1, 2, 2, 1 };

	if (horse == soldier)
	{
		return count;
	}

	int leastCount{ 999'999'999 };
	for (int i = 0; i < 8; i++)
	{
		Point newPos{ horse };
		newPos.x += xMoveDir[i];
		newPos.y += yMoveDir[i];

		if (IsOutOfBoard(newPos, n, m)
			|| visited[newPos.y][newPos.x] <= count)
		{
			continue;
		}

		visited[newPos.y][newPos.x] = count;

		int curCount{ GetLeastMoveCount(visited, n, m, newPos, soldier, count + 1) };
		if (curCount < leastCount)
		{
			leastCount = curCount;
		}
	}
	
	return leastCount;
}

/// <summary>
/// 말이 보드 밖으로 나갔는지 여부를 반환한다.
/// </summary>
/// <param name="p">확인할 말의 좌표</param>
/// <returns>보드 밖으로 나갔는지 여부</returns>
bool Janggi::IsOutOfBoard(const Point& p, int n, int m)
{
	if (p.x < 1) return true;
	if (n < p.x) return true;
	if (p.y < 1) return true;
	if (m < p.y) return true;
	return false;
}

 

---

실행 결과 Success(100)

---

 

코드해설

보드의 특정 칸에 말이 도달했을 때 이동한 개수가 칸에 저장된 개수보다 작을 때만 이동을 허용하면 결과적으로 최소 이동 경로를 구할 수 있게 된다.

 

이를 위해 우선 보드에는 어떤 값이 들어와도 진행이 되도록 큰 값을 입력해둔다.

	int** visited = new int* [m + 1];
	for (int i = 1; i <= m; i++)
	{
		visited[i] = new int[n + 1];
		for (int j = 1; j <= n; j++)
		{
			visited[i][j] = 999'999'999;
		}
	}

 

말의 이동이 보드 밖으로 나간 경우 혹은 너무 돌아와서 효율이 좋지 않은 경우 이동하지 않도록 한다.

		if (IsOutOfBoard(newPos, n, m)
			|| visited[newPos.y][newPos.x] <= count)
		{
			continue;
		}

 

※ 기존 말을 두는 문제와 달리 말이 이동하는 경우이므로 이동후에 값을 다시 초기화하지 않는다.

 

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermediate_Coder/백트래킹-DFS/장기-JUNGOL