JUNGOL...162

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],
		int** visited,
		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 };

	int** visited = new int* [n + 1];
	for (int i = 0; i <= n; i++)
	{
		visited[i] = new int[m + 1];
		for (int j = 0; j <= m; j++)
		{
			visited[i][j] = 999'999'999;
		}
	}
	std::cout << GetLeastMoveCount(xMoveDir, yMoveDir, 
		visited, false,
		n, m, r, c, s, k);
	for (int i = 0; i <= n; i++)
	{
		delete[] visited[i];
	}
	delete[] visited;
}

int Janggi::GetLeastMoveCount(int xMoveDir[8], int yMoveDir[8], 
	int** visited,
	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 };
	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] <= count)
		{
			continue;
		}

		visited[newR][newC] = count;

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

 

---

실행 결과 Wrong Answer(0)

원인 구글링 결과 한 번 진입한 위치에 다시 진입할 때는 이전에 진입했을 때의 개수보다 작을 때 진입이 가능하도록 수정하여 시간은 맞출 수 있었다. 하지만 답을 내지 못하고 있다.

처리 방법 우선 코드를 정리해서 알아보기 쉽게 만든 다음 다시 생각해 봐야겠다.

---

 

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

NadanKim/CodingTest_JUNGOL

 

문제출처

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