-
JUNGOL...161일지 2021. 11. 16. 21:13
Intermediate_Coder/백트래킹-DFS/장기
문제
N×M장기판에 졸 한개와 말 한개가 놓여 있다. 말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다.
말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자.
입력 형식
첫 줄은 장기판 행의 수(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)