육각형 우리 속의 개미
문제 해석
정육각형이 서로 맞닿은 형태의 개미 우리가 있을 때, 방향을 정확히 N번 회전하여 탐색을 멈추는 경우의 수를 구하는 문제입니다.
임의의 점에서 임의의 방향으로 되어있을 때, 세갈래길이 나오는 지점에서 회전을 하게 됩니다.
이동경로를 따라서 페로몬을 뿌리고 다니며, 개미가 페로몬이 이미 뿌려진 지점에 도착하면 탐색을 멈춥니다.
설계(20)
- 범위가 적어서 완전탐색으로 풀이가 가능해 보입니다.
- 우선, 육각형 맵을 구현합니다.
- 패턴은 세로로 4칸마다 반복됩니다.
- 첫번째와 네번째 칸은 0과 1이 순서대로 반복됩니다.
- 나머지 칸은 1과 0이 순서대로 반복됩니다.
- 최대 22번 회전을 해야하므로 한 방향으로 계속 이동한다고 생각하면 22x2칸 정도가 필요합니다.
- 중심좌표 기준으로 44칸정도가 필요하기 때문에 넉넉히 100x100으로 충분히 커버가 가능합니다.
- 경우의 수를 구하는데 백트래킹 기법을 사용합니다.
- 매개변수는 {이전좌표, 현재좌표,회전한 횟수}로 되어있습니다.
- 현재 좌표 기준으로 6방향에서 이동할 수 있는 경로인 경우만 탐색하도록 합니다.
- 바로 이전에 있던 좌표로 되돌아가지 않게 합니다.
- 또한, N번을 회전하지도 않았는데 방문한 곳을 다시 방문하는 경우 return 하도록 하였습니다.
- 정확히 N번 방문했을 때, 해당 좌표가 방문한 좌표이면 경우의수를 더하도록 하였습니다.
구현(30)
코드
#include <iostream>
#define MAXN 100
using namespace std;
int map[MAXN][MAXN];
bool visited[MAXN][MAXN];
int dx[] = {-1,-1,1,1,1,-1};
int dy[] = {0,1,1,0,-1,-1};
int N;
int ans;
void backtrack(int sx, int sy, int ex, int ey,int cnt){
if (cnt == N){
if (visited[ex][ey]) {
ans++;
}
return;
}
if (cnt <N && visited[ex][ey]) return;
visited[ex][ey] = true;
for (int i = 0 ; i < 6; i++){
int nx = ex + dx[i];
int ny = ey + dy[i];
if (nx == sx && ny == sy) continue;
if (map[nx][ny]){
backtrack(ex,ey,nx,ny,cnt+1);
}
}
visited[ex][ey] = false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 0 ; i< MAXN; i++){
int start = 0;
if (i%4 ==0 || i%4 == 3){
start = 1;
}
for (int j = start; j <MAXN; j+=2){
map[i][j] = 1;
}
}
visited[50][50] = true;
backtrack(50,50,49,50,0);
cout << ans <<"\n";
return 0;
}
디버깅
- N번 회전하기 전에 방문한 곳을 다시 방문하는 경우를 고려하지 않는 실수를 하였습니다.
제출결과
- 36 ms
마무리
- 완전탐색으로 풀이가 가능한 문제였습니다.
- 다른 분들의 풀이를 보니, DP로도 풀이가 가능한 것 같습니다.