JUNGOL...161

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:
	int GetLeastMoveCount(int xMoveDir[8], int yMoveDir[8],
		bool visited[101][101], bool isIn,
		int n, int m, int r, int c, int s, int k, int count = 0);
};

 

Janggi.cpp

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

	int r, c, s, k;
	std::cin >> r >> c >> s >> k;

	int xMoveDir[8]{ -2, -1, 1, 2, 2, 1, -1, -2 };
	int yMoveDir[8]{ -1, -2, -2, -1, 1, 2, 2, 1 };

	bool visited[101][101]{};
	std::cout << GetLeastMoveCount(xMoveDir, yMoveDir, 
		visited, 
		n, m, r, c, s, k);
}

int Janggi::GetLeastMoveCount(int xMoveDir[8], int yMoveDir[8], 
	bool visited[101][101],
	int n, int m, int r, int c, int s, int k, int count)
{
	if (r == s && c == k)
	{
		return count;
	}

	int leastCount{ 999'999'999 };

	if (std::abs(r - s) <= 3 && std::abs(c - k) <= 3)
	{
		for (int i = 0; i < 8; i++)
		{
			int newR{ r + xMoveDir[i] }, newC{ c + yMoveDir[i] };
			if (newR < 1 || newR > n || newC < 1 || newC > m
				|| visited[newR][newC])
			{
				continue;
			}

			visited[newR][newC] = true;

			int curCount{ GetLeastMoveCount(xMoveDir, yMoveDir,
				visited,
				n, m, newR, newC, s, k, count + 1) };
			if (curCount < leastCount)
			{
				leastCount = curCount;
			}

			visited[newR][newC] = false;
		}
	}
	else
	{
		int newR{ r }, newC{ c };
		int dist{ 999'999 };
		for (int i = 0; i < 8; i++)
		{
			int xDiff{ r + xMoveDir[i] - s }, yDiff{ c + yMoveDir[i] - k };
			int curDist{ xDiff * xDiff + yDiff * yDiff };
			if (curDist < dist)
			{
				dist = curDist;
				newR = r + xMoveDir[i];
				newC = c + yMoveDir[i];
			}
		}

		visited[newR][newC] = true;

		int curCount{ GetLeastMoveCount(xMoveDir, yMoveDir,
			visited,
			n, m, newR, newC, s, k, count + 1) };
		if (curCount < leastCount)
		{
			leastCount = curCount;
		}

		visited[newR][newC] = false;
	}
	
	return leastCount;
}

 

---

실행 결과 Time Limit Exceed(0)

원인 거리가 멀 때는 해당 방향으로 최대한 가깝게 가는 방향을 선택하도록 하고 근처에 도달한 경우 8 방향을 확인하면서 도착하도록 했으나 여전히 적절하게 찾지 못하고 있다.

처리 방법 구글링 해서 어떤 식으로 생각을 해야하는지 찾아봐야 할 것 같다.

---

 

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

NadanKim/CodingTest_JUNGOL

 

문제출처

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