폴리매스

다시 돌아오는 것도 가능한가요? 즉, 그 경우도 포함인가요??

나이트가 말모양으로 장기의 말과 가는 칸 수가 같죠?

프로그래밍 해보긴 했는데 4개 이상은 컴퓨터 성능이 매우 뛰어나지 않은 이상 도저히 안 됩니다. 아직 약간의 오류가 있어서 수정한 뒤에 알려드리겠습니다.

#include <stdio.h>

int count=0, x=0, y=0;
int a[10000]={0,};
int b[10000]={0,};
int c, d;
int move(int i){
 int j, t;
 if(i>0){
  c=x, d=y; x+=2, y++; move(i-1);
  c=x, d=y; x+=2, y--;  move(i-1);
  c=x, d=y; x-=2, y++; move(i-1);
  c=x, d=y; x-=2, y--; move(i-1);
  c=x, d=y; x++,y+=2;move(i-1);
  c=x, d=y; x++, y-=2; move(i-1);
  c=x, d=y; x--, y+=2; move(i-1);
  c=x, d=y; x--, y-=2; move(i-1);
  return count;
 }
 if(i<=0){
  t=1;
  for(j=0;j<=count;j++){
   if((a[j]==x)&&(b[j]==y)){
    t=0; break;
   }
   break;
  }
  if(t){
   a[count]=x; b[count]=y;
   count++;
   x=c, y=d;
  }
 }
}
void main(){
 int n;
 for(n=1;n<=3;n++)
  printf("n=%d : %d\n", n, move(n));
}

오류가 완벽하게 수정되지는 않았습니다. n=2일 때 65라고 결과가 나오니까요.........

오류 수정했습니다. 정답이 맞는지는 모르겠습니다.

#include <stdio.h>
int count=0, x=0, y=0;
int a[10000]={0,} , b[10000]={0,};
int c, d;
int move(int i){
 int j, t;
 if(i>0){
  c=x, d=y; x+=2, y++; move(i-1);
  c=x, d=y; x+=2, y--;  move(i-1);
  c=x, d=y; x-=2, y++; move(i-1);
  c=x, d=y; x-=2, y--; move(i-1);
  c=x, d=y; x++,y+=2;move(i-1);
  c=x, d=y; x++, y-=2; move(i-1);
  c=x, d=y; x--, y+=2; move(i-1);
  c=x, d=y; x--, y-=2; move(i-1);
  return count;
 }
 if(i<=0){
  t=1;
  for(j=0;j<count;j++){
   if((a[j]==x)&&(b[j]==y)){
    t=0; x=c; y=d; break;
   }
  }
  if(t){
   a[count]=x; b[count]=y;
   count++;
   x=c, y=d;
  }
 }
}
void main(){
 int n;
 for(n=1;n<=10;n++){
  count=0;
  for(x=0; x<=10000; x++){
   a[x]=0, b[x]=0;
  }
  x=0; y=0;
  printf("n=%d : %d\n", n, move(n));
 }
}

n=1일 때 : 8

n=2일 때 : 32

n=3일 때 : 68
 

출력 결과

이 이상은 구하는데 너무 오래 걸려요......... 재귀함수를 이용했는데 n에 따라 함수의 실행 횟수가 이나 되서..... 좀 빨리 실행할 수 있는 건 모르겠고, 이 코드에 대해 설명드릴게요

메인 함수에서, x의 좌표값과 y의 좌표값을 0으로 설정하고 move함수를 실행시킵니다. move함수에서는, 나이트가 이동할 수 있는 8가지 이동을 하나하나 실행하면서, n의 횟수, 즉 이동 횟수를 1씩 줄입니다. n이 0이 되면, 배열 a에 저장된 x좌표, b에 저장된 y좌표에 동시에 공통되는 것이 있는지 확인합니다. 있으면, count를 증가시키지 않고, 없으면, 배열에 저장시킨 후 count++를 합니다. 재귀호출된 함수가 8가지 이동을 모두 해보고, count를 반환하는데, 재귀호출된 함수에서는 반환값이 중요한 게 아니라, a배열과 b배열의 저장한 값, 그리고 count의 증가가 중요한 겁니다. 그리고 move함수가 모두 끝나고 나면, count를 반환합니다. 그래서 printf("n=%d : %d\n", n, move(n));이 구절에서 저런 형식으로 출력이 됩니다. count가 외부변수이기 때문에 굳이 반환할 필요는 없습니다.

중요한 점 : a배열, b배열, count, x,y, c, d는 모두 외부변수여야 합니다.내부변수인 경우에는 move함수를 호출할 떄마다 변수들이 초기화됩니다.

/// copyright by muse.

#include <bits/stdc++.h>

int n; /// 움직이는 횟수.

bool board[102][102]; /// 체스판. (50, 50)이 원점이라고 가정합니다.
bool DP[52][102][102]; /// 한 번 계산한 위치는 다시 계산하지 않게 처리합니다. 즉 한 번 계산한 위치에 표시를 해 놓습니다.

int xx[]={-2, -1, 1, 2, 2, 1, -1, -2}, yy[]={1, 2, 2, 1, -1, -2, -2, -1};
/// 나이트가 움직일 수 있는 칸 수를 설정해 놓은 배열입니다.

int ans; /// 답을 저장할 변수입니다.

void move(int i, int x, int y){ /// i는 지금까지 움직인 횟수, x, y는 위치.
    if(i==n){ /// n회 움직였을 때(즉 다 움직였을 때)
        board[x][y] = true; /// 체스판에 체크를 해 놓습니다.
        return; /// 함수를 종료합니다.
    }
    if(DP[i][x][y]) return; /// 이미 방문한 위치이면 함수를 종료합니다.
    DP[i][x][y] = true; /// 방문한 위치에 체크합니다.
    for(int a=0; a<8; a++){ /// 방문할 수 있는 모든 위치를
        move(i+1, x+xx[a], y+yy[a]); /// 방문합니다.
    }
    return; /// 모든 작업이 끝났으므로 프로그램을 종료합니다.
}

int main(){
    scanf("%d", &n); /// 움직일 횟수를 입력받습니다.
    move(0, 50, 50); /// 함수를 호출합니다.
    for(int i=1; i<=100; i++){
        for(int j=1; j<=100; j++){ /// 모든 칸을 방문하며
            ans += board[i][j]; /// 방문할 수 있는지를 체크합니다.
        }
    }
    printf("%d", ans); /// 결과를 출력합니다.
}
 

저는 수학장 님과는 다른 결과가 나오네요.

1: 8

2: 33

3: 76

4: 129

5: 196

6: 277

7: 372

8: 481

9: 604

10: 741

.....

24(구할 수 있는 최대): 4129.

그 이상은 답이 이상하게 나오거나 에러가 나옵니다.

정확히 n번 움직이는건가요 아니면 n번까지 움직일 수 있는 건가요?