JUNGOL/Intermediate_Coder/그래프탐색-BFS/4189 : 장기 2

Intermediate_Coder/그래프탐색-BFS/장기 2

---

문제                                            

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

JUNGOL 그래프탐색-BFS 장기 2

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

 

입력 형식                                     

첫 줄은 장기판 행의 수(N)와 열의 수(M)를 받는다

(1 ≤  N, M ≤ 1000).

둘째 줄은 말이 있는 위치의 행(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

---

Janggi2.h

#pragma once
#include <iostream>
#include <queue>

#include "../../Base.h"

using std::queue;

class Janggi2 : public Base
{
private:
	struct Point
	{
		Point() : x(0), y(0), count(0) {}

		int x, y;
		int count;

		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);
	bool IsOutOfBoard(const Point& p, int n, int m);

protected:
	void Code() override;
};

 

Janggi2.cpp

void Janggi2::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 Janggi2::GetLeastMoveCount(int** visited, int n, int m, Point horse, const Point& soldier)
{
	static int xMoveDir[8]{ -2, -1, 1, 2, 2, 1, -1, -2 };
	static int yMoveDir[8]{ -1, -2, -2, -1, 1, 2, 2, 1 };

	queue<Point> q;

	q.push(horse);

	int leastCount{ 999'999'999 };
	while (!q.empty())
	{
		Point p{ q.front() };
		q.pop();

		if (p == soldier)
		{
			if (p.count < leastCount)
			{
				leastCount = p.count;
			}
		}

		for (int i = 0; i < 8; i++)
		{
			Point newPos{ p };
			newPos.x += xMoveDir[i];
			newPos.y += yMoveDir[i];
			newPos.count = p.count + 1;

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

			q.push(newPos);

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

	return leastCount;
}

/// <summary>
/// 말이 보드 밖으로 나갔는지 여부를 반환한다.
/// </summary>
/// <param name="p">확인할 말의 좌표</param>
/// <returns>보드 밖으로 나갔는지 여부</returns>
bool Janggi2::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)

---

 

코드 해설

우선 BFS로 풀어야 하므로 queue를 사용해야 한다.

이때, 각각의 지점이 몇 번의 이동으로 도달한 것인지를 저장해 둬야 하므로 Point에 이동 횟수를 기록할 변수가 필요하다.

	struct Point
	{
		Point() : x(0), y(0), count(0) {}

		int x, y;
		int count;

 

이후 8방향으로 이동하면서 병사에 도달한 경우 이동 횟수를 기록하고 그 중 가장 작은 값을 저장한다.

		if (p == soldier)
		{
			if (p.count < leastCount)
			{
				leastCount = p.count;
			}
		}

		for (int i = 0; i < 8; i++)
		{
			Point newPos{ p };
			newPos.x += xMoveDir[i];
			newPos.y += yMoveDir[i];
			newPos.count = p.count + 1;

 

이때, 같은 위치로 다시 돌아가는 경우 무한루프에 빠지게 되므로 돌아가지 않도록 이전 위치가 몇 번의 이동으로 도달했는지를 기록해 둬야 한다.

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

			q.push(newPos);

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

 

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

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermediate_Coder/그래프탐색-BFS/장기2-JUNGOL