Random Walk

'술취한 바퀴벌레' 문제라고도 한다. 다음과 같은 격자에 술취한 바퀴벌레가 있다고 해 보자

. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .

바퀴벌레는 임의의 한 점에서 시작하여서 임의의 방향으로 움직이게 된다. 이미 지나갔던 자리에 다시 갈 수 있으며 프로그램은 바퀴벌레가 각 위치에 몇번 갔는지 기억하여야 한다. 프로그램은 바퀴벌레가 모든 지점에 적어도 한번 이상 도달하였을 경우 끝난다. 바퀴벌레는 가로, 세로, 대각선으로 한칸 씩만 움직일수 있으며, 바퀴벌레가 움직이는 방향을 랜덤하게 만드는 것은 각자가 생각해 보도록 한다.

입력

격자의 가로, 세로 크기, 바퀴벌레의 초기 위치

출력

각 칸에 바퀴벌레가 멈추었던 횟수, 바퀴벌레가 움직인 횟수.

심화문제

격자의 가로, 세로의 크기를 입력받을때. 엄청나게 큰 크기를 입력하면 어떻게 할 것인가?


참고

출처: 위키백과

무작위 행보(無作爲行步, random walk, 랜덤 워크)는 수학, 컴퓨터 과학, 물리학 분야에서 임의 방향으로 향하는 연속적인 걸음을 나타내는 수학적 개념이다. 무작위 행보(random walk)라는 개념은 1905년 Karl Pearson이 처음 소개하였으며 생태학, 수학, 컴퓨터 과학, 물리학, 화학 등의 분야에서 광범위하게 사용되고 있다.

랜덤 워크는 시간에 따른 편차의 평균이 0이지만 분산은 시간에 비례하여 증가하게 된다. 따라서, 앞 뒤로 움직일 확률이 동일하다고 해도 시간이 흐름에 따라 평균에서 점차 벗어나는 경향을 보인다.

대표적인 예로는 브라운 운동이 있으며, "술고래의 걸음"이라고도 한다.

저 질문있어요^^; 출력에서 바퀴벌레가 움직인 횟수는 무엇을 말하는 것인가요?;ㅋㅋㅋ 혹시 바퀴벌레가 일직선으로 움직일때(들어온방향과 나간방향이 같을때) 바퀴벌레가 그 칸을 움직인거고, 그 칸에서 방향을 바꿨다면 그 칸에서 멈춘건가요? 각 칸에 바퀴벌레가 지나간 횟수가 최소화된다 뭐 이런 조건 없이 마음대로 랜덤하게 짜면 되는건가요? - Katherine, 2014/03/10 10:02 M D
@Katherine님, 바퀴벌레가 움직인 횟수는 바퀴벌레가 칸을 이동한 총 횟수이구요, 각 칸에 바퀴벌레가 멈추었던 횟수는 바퀴벌레가 몇번 그 칸에 들렀는지라고 보면 될것 같습니다. 네, 최소화 조건은 없구요, 바퀴벌레 자유의지에 의해서 랜덤하게 만드시면 됩니다. ^^ - 길가의풀, 2014/03/10 10:35 M D
@길가의풀 네 알겠어요^^ 감사합니다^^ - Katherine, 2014/03/10 11:05 M D
+1 Programming Challenge 자체가 현재 판매중인 프로그래밍 문제 책이고 사이트는 그 책의 문제들을 채점해볼 수 있는 공간을 제공하기 위한 것 아닌가요? 저작권 문제가 되지 않을지? - Kim Jaeju, 2014/03/10 13:55 M D
@Kim Jaeju 님, 아.. 저작권 문제가 될 수도 있을것 같네요, 생각도 못 해 봤는데요.. 저작권에 대해서는 잘 검토 해 보도록 하겠습니다. 알려주셔서 감사합니다. - 길가의풀, 2014/03/10 14:04 M D
@Kim Jaeju 님, Programming Challenge 저자(Miguel A. Revilla Ramos씨)에게 문의한 결과, Academic한 사용으로는 제한없이 사용할 수 있다는 답장을 받았네요 ^^. - 길가의풀, 2014/03/10 19:52 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

1개의 풀이가 있습니다.

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

void RandomMove(int ** matrix, int * x, int * y, int m, int n, long long * remaining_boxes);
void printMatrix(int ** matrix, int m, int n);
void moveMatrix(int ** matrix, int x, int y, int m, int n, long long * remaining_boxes);

int main(int argc, char* argv[])
{
    int m =0, n=0, x =0, y =0;
    int ** matrix;
    int i=0;
    long long total = 0, remaining_boxes=0, loop_count=0, loop_loop_count = 0;
    int temp_count = 0, remaining_change = 0, temp_rem = 0;
    time_t start,end; 
    double diff;
    double ratio;

    if (argc!=5) {
        printf("ERROR: Input argument missing. Usage: main 5 4 1 1");
        return 0;
    }

    m = atoi(argv[1]);
    n = atoi(argv[2]);
    x = atoi(argv[3]);
    y = atoi(argv[4]);

    if (x >= m){
        printf("ERROR: x muse be smaller than m value. x:%d, m:%d\n", x, m);
        return 0;
    }
    if (y >= n){
        printf("ERROR: y muse be smaller than n value. y:%d, n:%d\n", y, n);
        return 0;
    }
    remaining_boxes = m * n;
    total = remaining_boxes;    

    srand((unsigned)time(NULL)+(unsigned)getpid());
    if ((matrix = (int **)calloc(m, sizeof(int))) == NULL ) {
        printf("Array allocation of size of %d has failed.\n", m*n);

        return 0;
    }

    for (i=0; i<m; i++){
        if ((matrix[i] = (int *)calloc(n, sizeof(int))) == NULL ) {
            printf("Array allocation of size of %d has failed.\n", m*n);
            return 0;
        }
    }   
    matrix[x][y]=1;
    remaining_boxes--;
//  Initialization has been finished.

    time (&start);
    while (remaining_boxes > 0) {
        temp_rem = remaining_boxes;
        RandomMove(matrix, &x, &y, m, n, &remaining_boxes);
        if (temp_rem == remaining_boxes)
            temp_count++;
        else
            temp_count=0;
        if (loop_count == 100000000) {
            loop_loop_count++;
            loop_count=0;
        }
        else 
            loop_count++;
        if (temp_count > 50000) {
            temp_count = 0;
            srand((unsigned)time(NULL)+(unsigned)getpid());
        }
    }
    time (&end);
//  Random walk has been finished.

//  printMatrix(matrix, m, n)
    printf("Random walk simulation has finished.\n");
    printf("Last location of mouse is (%d, %d).\n", x, y);
    if (loop_loop_count > 0){
        printf("Total number of move is  %lld * 100,000,000 + ", loop_loop_count);  
        printf("%lld\n", loop_count);
    }
    else {  
        printf("Total number of move is  %lld.\n+", loop_count);  
    }
    diff = difftime (end,start); 
    printf ("Elasped time : %.2lf seconds.", diff ); 


//  Finilization begins
    for(i=0; i<m; i++){
        free(matrix[i]);
    }
    free(matrix);

    return 0;
}   

void RandomMove(int ** matrix, int * x, int * y, int m, int n, long long * remaining_boxes)
{
    int r = 0, done = 0;

    while (done == 0) {
        r = rand()%8;
        switch(r) {
            case 0 :
                if(*x>=1 && *y>=1) {
                    moveMatrix(matrix, *x-1, *y-1, m, n, remaining_boxes);
                    *x=*x-1;
                    *y=*y-1;
                    done = 1;
                    break;
                }
                else    
                    break;
            case 1 : 
                if(*x>=1) {
                    moveMatrix(matrix, *x-1, *y, m, n, remaining_boxes);
                    *x=*x-1;
                    done = 1;
                    break;
                }
                else    
                    break;
            case 2 : 
                if(*x>=1 && *y <=n-2 ) {
                    moveMatrix(matrix, *x-1, *y+1, m, n, remaining_boxes);
                    *x=*x-1;
                    *y=*y+1;
                    done = 1;
                    break;
                }
                else    
                    break;  
            case 3 : 
                if(*y >=1 ) {
                    moveMatrix(matrix, *x, *y-1, m, n, remaining_boxes);
                    *y=*y-1;
                    done = 1;
                    break;
                }
                else    
                    break;
            case 4 : 
                if(*y <=n-2 ) {
                    moveMatrix(matrix, *x, *y+1, m, n, remaining_boxes);
                    *y=*y+1;
                    done = 1;
                    break;
                }
                else    
                    break;
            case 5 :
                if(*x<=m-2 && *y>=1) {
                    moveMatrix(matrix, *x+1, *y-1, m, n, remaining_boxes);
                    *x=*x+1;
                    *y=*y-1;
                    done = 1;
                    break;
                }
                else    
                    break;
            case 6 : 
                if(*x<=m-2) {
                    moveMatrix(matrix, *x+1, *y, m, n, remaining_boxes);
                    *x=*x+1;
                    done = 1;
                    break;
                }
                else    
                    break;
            case 7 : 
                if(*x<=m-2 && *y <= n-2) {
                    moveMatrix(matrix, *x+1, *y+1, m, n, remaining_boxes);
                    *x=*x+1;
                    *y=*y+1;
                    done = 1;
                    break;
                }
                else    
                    break;
            default :
                break;
        }
    }
}

void moveMatrix(int ** matrix, int x, int y, int m, int n, long long * remaining_boxes)
{
    if (matrix[x][y]==0) {
        matrix[x][y]++;
        (*remaining_boxes)--;
    }
    else {
        matrix[x][y]++;
    }
}

void printMatrix(int ** matrix, int m, int n)
{
    int i, j;

    for (i=0; i<m; i++){
        for(j=0; j<n; j++){
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

  • 처음 작성해봤습니다. 동적으로 matrix를 생성하고, 초기 위치는 입력받는 걸로 해봤습니다.
  • 총 이동 횟수가 수십억이 넘어가니 자릿수를 벗어나네요.. Big Number를 구현하기 보다는, 그냥 되는데로 자릿수 나눠서 카운트해봤습니다.
  • 100x100은 1초도 안걸리고, 2,000x2,000은 1,347초 걸리네요..

D:\Codes\RandomWalk>main 100 100 0 0 Random walk simulation has finished. Last location of mouse is (7, 0). Total number of move is 214380. +Elasped time : 0.00 seconds.

D:\Codes\RandomWalk>main 2000 2000 0 0 Random walk simulation has finished. Last location of mouse is (943, 745). Total number of move is 420 * 100,000,000 +21472115 Elasped time : 1347.00 seconds.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 27
python x 15
cs x 2
r x 1
matlab x 1
기 타 x 2
java x 4
cpp x 1
ruby x 1