문제
n * m 체스보드에서 기사의 여행 문제를 해결하는 백트래킹 알고리즘을 구현하시오.
Knight's Tour 문제는 해밀턴 경로(path)와 해밀턴 회로(circuit, cycle)를 찾는 문제로 구분할 수 있다.
해밀턴 회로는 출발 정점과 무관하게 회로의 수를 구할 수 있고,
해밀턴 경로는 출발 정점에 따라 가능한 경로의 수가 달라짐에 유의하시오.
입력
첫 번째 줄에 체스보드의 크기 n(행의 크기)과 m(열의 크기)이 주어진다.
두 번째 줄에 출발 정점의 개수 T가 주어진다.
이후로 T개의 출발정점이 i(row), j(col)의 쌍으로 주어진다.
출력
첫 번째 줄에 해밀턴 회로의 개수를 출력한다.
두 번째 줄부터 입력에서 주어진 출발정점 각각에 대해 해밀턴 경로의 수를 한 줄에 하나씩 출력한다.
문제 해석
- 해미털 회로와 경로의 차이를 알아야 한다.
- 해밀턴 회로란 출발 정점에서 모든 정점을 각 한 번씩 방문하고 다시 출발 정점으로 돌아와야 한다.
- 해밀턴 경로란 출발 정점에서 모든 정점을 각 한 번씩 방문하기만 하면 된다. (다시 출발점으로 돌아올 필요가 없음.)
- knight의 이동반경을 알아야 한다.
- 문제에서 knight는 체스에서 knight를 의미하며 kngiht가 갈 수 있는 방향은 아래 그림과 같다.
- 자기 자신을 기준으로 8방향을 갈 수 있다.
3. n*m 체스판을 행렬로 만들면 n, m의 값이 커지면 시간이 오래 걸림
--> 자료구조를 행렬이 아닌 인접 리스트를 선택.
grpah [n][m] 배열이 아닌 size가 n*m인 일차원 배열을 만들어준다.
1차원 vector visit를 만들어주고 visit의 size는 n*m+1이 될 것이다. 1~25까지 있어야 하기 때문이다.
만약 n번지를 방문했다면 visit [n]=1로 초기화해준다.
각 위치마다 나이트의 이동 법칙에 의해서 갈 수 있는 경로가 있다.
location 1 : [8,12], location 2 : [11,9,13] 등등이 있을 것이다. 그때의 location을 i로 , j를 갈 수 있는 위치로 가정하고
graph [i][j]를 1로 초기화시켜준다. graph값이 1이라는 뜻은 갈 수 있는 경로라는 뜻이다.
예를 들어 graph [1][8]은 1에서 8까지 갈 수 있으므로 값은 1이 된다. 하지만 graph [1][7]은 경로가 없으므로 0이다.
4. 가지치기 조건을 이용해서 재귀 함수를 사용, 결과를 도출.
- 만약 경로가 없는 곳이라면? 방문 x
- 경로가 있더라도, 이미 방문한 곳을 또 방문할 예정이라면, 그 방문은 불필요하기 때문에 탐색 x
- 만약 마지막 노드를 방문했는데, 그 마지막 노드와 출발점이 연결이 안 되어있다면, 회로 추가 x
- 마지막 노드를 방문할 차례고, 지금 방문하려는 노드와 직전에 방문한 노드가 경로가 있고, 각 한 번씩 방문한 노드라면, 경로 추가
구현
1. 해당되는 나이트의 경로마다 연결해주기
void Move(int i)
{
int row = i / m;
int col = i % m;
if (row - 2 >= 0 && col - 1 >= 0)
{
graph[i][(row - 2) * m + col - 1] = 1;
graph[(row - 2) * m + col - 1][i] = 1;
}
if (row - 2 >= 0 && col + 1 <= m - 1)
{
graph[i][(row - 2) * m + col + 1] = 1;
graph[(row - 2) * m + col + 1][i] = 1;
}
if (row + 2 <= n - 1 && col + 1 <= m - 1)
{
graph[i][(row + 2) * m + col + 1] = 1;
graph[(row + 2) * m + col + 1][i] = 1;
}
if (row + 2 <= n - 1 && col - 1 >= 0)
{
graph[i][(row + 2) * m + col - 1] = 1;
graph[(row + 2) * m + col - 1][i] = 1;
}
if (row + 1 <= n - 1 && col - 2 >= 0)
{
graph[i][(row + 1) * m + col - 2] = 1;
graph[(row + 1) * m + col - 2][i] = 1;
}
if (row + 1 <= n - 1 && col + 2 <= m - 1)
{
graph[i][(row + 1) * m + col + 2] = 1;
graph[(row + 1) * m + col + 2][i] = 1;
}
if (row - 1 >= 0 && col + 2 <= m - 1)
{
graph[i][(row - 1) * m + col + 2] = 1;
graph[(row - 1) * m + col + 2][i] = 1;
}
if (row - 1 >= 0 && col - 2 >= 0)
{
graph[i][(row - 1) * m + col - 2] = 1;
graph[(row - 1) * m + col - 2][i] = 1;
}
}-> 각 출발지마다 갈 수 있는 경로는 1로 초기화된다.
2. 가지치기 함수
bool promising(int i, int node, int start) //방문한곳이면 안간다. 그리고 갈 수있는 곳은 미리 체크하는게 나을까? 경로가 없으면 0 경로가 있으면 1이다. node가 내가 갈곳 start는 내가있는곳
{
//마지막 정점일때는 거기서 출발점까지의 경로가 무조건 있어야함.
bool flag = true;
bool opt;
int now = 0;
if (i == Size && graph[visit[Size]][start] != 1) //회로는 출발점을 다시 돌아와야함. //visit[Size]가 맨 마지막에 방문한 노드일거다 아마.
{
flag = false;
}
if (i == Size && graph[visit[i]][visit[i - 1]] == 1) //경로는 출발점을 다시 안와도됨. //이미 방문한 노드여도 cnt가 ++됨.
{
opt = true; //초기는 하고 만약에 같은게 없다면 flag는 true이므로
for (int k = 0; k < i; k++) // Size를 i보다 작을때로 바꿈 자기자신은 검사할필요가없네
{
// cout << visit[k] << " ";
if (visit[i] == visit[k]) //이미 방문한 곳이라면
{
opt = false;
flag = false;
}
} //반복문이 안걸리고 나오면 트루라는뜻
if (opt == true)
{
Cnt++;
}
}
else if (i > 0 && graph[visit[i]][visit[i - 1]] != 1) //연결안되어있는건 걍 재낌.
{
flag = false;
}
else //연결되어있다면 방문했는지 안했는지 체크를 해야함.
{
flag = true;
while (now < i)
{
if (visit[now] == visit[i])
{
flag = false;
}
now++;
}
}
return flag;
}
3. 모든 노드를 방문하는 함수(적절한 가지치기를 통해서 불필요한 탐색 x)
void knight(int i, int node, int start, int now)
{
bool opt = true;
if (promising(i, node, start)) // node는 내가 가려는 곳 start는 출발 정점.
{
if (i == n * m - 1)
{
cnt++;
}
else
{
for (int j = 0; j <= Size; j++)
{
// visit[i]기준으로 갈 수 있는 방향을 선정해야함.
if (graph[visit[i]][j] == 1) //경로가 있고
{
visit[i + 1] = j;
knight(i + 1, j, start, visit[i]); // knight탈출하면 방문안햇다는 뜻임.
visit[i + 1] = 0;
}
}
}
}
}
전체 코드
/*
1.해밀턴의 회로의 수는 어디서 출발하든 같다.
2.해밀턴 회로란 출발점에서 모든 노드를 방문하고 마지막에 다시 출발점으로 오는 경로의수다. 여기서 주의할점은 모든 노드를 딱 한번만 방문해야한다는점이다.
3.하지만 해밀턴 경로의 수는 출발정점에 따라 다르다.
4.정점의 수는 n*m이다. 종료 조건은 i가 n*m이 될떄이면 될것이다.
5.kngiht가 이동할 수 있는 방향은 8가지이다.
6.나이트가 정점마다 갈 수있는 경로를 뽑는게 좋을거같은데
7.체스판을 0번부터 n*m-1번까지 1차원 배열로 만든다.
8.각 정점마다 갈 수 있는 수는
*/
//해밀턴회로만 신경쓰자.
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int n, m, T, cnt = 0, Cnt;
vector<int> visit;
int Size;
vector<vector<int>> graph;
void Move(int i);
void knight(int i, int node, int start, int now);
bool promising(int i, int node, int first);
int main()
{
cin >> n >> m; // n은 row, m은 col
Size = n * m - 1;
visit.resize(n * m);
// Visit.resize(n * m);
graph.resize(n * m, vector<int>(m * n, 0));
for (int i = 0; i <= Size; i++)
{
Move(i); //
}
knight(0, 0, 0, 0);
visit.resize(n * m, 0);
cout << cnt << endl;
Cnt = 0;
cin >> T;
for (int i = 0; i < T; i++)
{
int s, f;
cin >> s >> f;
int vv = s * m + f;
visit[0] = vv;
knight(0, 0, vv, 0); // i,node,start,now
if (i < T - 1)
{
cout << Cnt << endl;
}
else
cout << Cnt;
Cnt = 0;
}
}
void knight(int i, int node, int start, int now)
{
bool opt = true;
if (promising(i, node, start)) // node는 내가 가려는 곳 start는 출발 정점.
{
if (i == n * m - 1)
{
cnt++;
}
else
{
for (int j = 0; j <= Size; j++)
{
// visit[i]기준으로 갈 수 있는 방향을 선정해야함.
if (graph[visit[i]][j] == 1) //경로가 있고
{
visit[i + 1] = j;
knight(i + 1, j, start, visit[i]); // knight탈출하면 방문안햇다는 뜻임.
visit[i + 1] = 0;
}
}
}
}
}
bool promising(int i, int node, int start) //방문한곳이면 안간다. 그리고 갈 수있는 곳은 미리 체크하는게 나을까? 경로가 없으면 0 경로가 있으면 1이다. node가 내가 갈곳 start는 내가있는곳
{
//마지막 정점일때는 거기서 출발점까지의 경로가 무조건 있어야함.
bool flag = true;
bool opt;
int now = 0;
if (i == Size && graph[visit[Size]][start] != 1) //회로는 출발점을 다시 돌아와야함. //visit[Size]가 맨 마지막에 방문한 노드일거다 아마.
{
flag = false;
}
if (i == Size && graph[visit[i]][visit[i - 1]] == 1) //경로는 출발점을 다시 안와도됨. //이미 방문한 노드여도 cnt가 ++됨.
{
opt = true; //초기는 하고 만약에 같은게 없다면 flag는 true이므로
for (int k = 0; k < i; k++) // Size를 i보다 작을때로 바꿈 자기자신은 검사할필요가없네
{
// cout << visit[k] << " ";
if (visit[i] == visit[k]) //이미 방문한 곳이라면
{
opt = false;
flag = false;
}
} //반복문이 안걸리고 나오면 트루라는뜻
if (opt == true)
{
Cnt++;
}
}
else if (i > 0 && graph[visit[i]][visit[i - 1]] != 1) //연결안되어있는건 걍 재낌.
{
flag = false;
}
else //연결되어있다면 방문했는지 안했는지 체크를 해야함.
{
flag = true;
while (now < i)
{
if (visit[now] == visit[i])
{
flag = false;
}
now++;
}
}
return flag;
}
void Move(int i)
{
int row = i / m;
int col = i % m;
if (row - 2 >= 0 && col - 1 >= 0)
{
graph[i][(row - 2) * m + col - 1] = 1;
graph[(row - 2) * m + col - 1][i] = 1;
}
if (row - 2 >= 0 && col + 1 <= m - 1)
{
graph[i][(row - 2) * m + col + 1] = 1;
graph[(row - 2) * m + col + 1][i] = 1;
}
if (row + 2 <= n - 1 && col + 1 <= m - 1)
{
graph[i][(row + 2) * m + col + 1] = 1;
graph[(row + 2) * m + col + 1][i] = 1;
}
if (row + 2 <= n - 1 && col - 1 >= 0)
{
graph[i][(row + 2) * m + col - 1] = 1;
graph[(row + 2) * m + col - 1][i] = 1;
}
if (row + 1 <= n - 1 && col - 2 >= 0)
{
graph[i][(row + 1) * m + col - 2] = 1;
graph[(row + 1) * m + col - 2][i] = 1;
}
if (row + 1 <= n - 1 && col + 2 <= m - 1)
{
graph[i][(row + 1) * m + col + 2] = 1;
graph[(row + 1) * m + col + 2][i] = 1;
}
if (row - 1 >= 0 && col + 2 <= m - 1)
{
graph[i][(row - 1) * m + col + 2] = 1;
graph[(row - 1) * m + col + 2][i] = 1;
}
if (row - 1 >= 0 && col - 2 >= 0)
{
graph[i][(row - 1) * m + col - 2] = 1;
graph[(row - 1) * m + col - 2][i] = 1;
}
}느낀 점 :
너무 불필요하게 길게 짠 것 같다. backtracking에서 가지치기를 효율적으로 짜야 알고리즘의 효율성이 높아지는데 내가 짠 가지치기의 조건과 방법이 조금 너무 노가다(?)가 아니었나 싶다.. ㅎ,, 다른 사람 코드를 보고 많이 반성했다.
'Skils > Algorithm' 카테고리의 다른 글
| [알고리즘-C++] 분기한정(Branch & Bound)를 이용한 0-1 배낭 채우기 (1) | 2022.05.28 |
|---|---|
| [C++] 알고리즘 이론 - Branch & Bound (분기 한정) (0) | 2022.05.28 |
| 알고리즘[C++] 0-1 knapsack problem with Backtracking(백트래킹) (0) | 2022.05.23 |
| 알고리즘[C++] 0-1 knapsack with 동적계획법(Dynamic programming) (0) | 2022.05.22 |
| 알고리즘[C++]-Hamiltonian Problem(해밀턴 회로 문제) (2) | 2022.05.16 |
