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
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

27개의 풀이가 있습니다. 3 / 3 Page

# 파이썬 3.5.1

from random import *

def do(xl,yl,x,y):
    c = 0
    mat = [[0 for i in range(xl)] for i in range(yl)]
    direc = {0:(0,-1),1:(1,-1),2:(1,0),3:(1,1),4:(0,1),5:(-1,1),6:(-1,0),7:(-1,-1)}
    while True:
        matstr = ''
        matstt = ''
        for i in mat:
            i = list(map(str,i))
            matstt += ' ' + ' '.join(i) + ' \n'
            matstr += ' '.join(i) + '\n'
        if x == 1:
            if y == 1:
                di = choice([2,3,4])
            elif y == yl:
                di = choice([0,1,2])
            else:
                di = choice([0,1,2,3,4])
        elif x == xl:
            if y == 1:
                di = choice([4,5,6])
            elif y == yl:
                di = choice([6,7,0])
            else:
                di = choice([4,5,6,7,0])
        else:
            if y == 1:
                di = choice([2,3,4,5,6])
            elif y == yl:
                di = choice([0,1,2,6,7])
            else:
                di = choice([0,1,2,3,4,5,6,7])
        mat[x-1][y-1] += 1
        x += direc[di][0]
        y += direc[di][1]
        if matstt.count(' 0 ') == 0:
            return matstr,c
        c += 1

xM,yM,x,y = map(int,input().split())
s,c = do(xM,yM,x,y)
print(s)
print(c)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

C#으로 작성했습니다. 위의 이우람 님의 코드를 도움 받아 작성했습니다. Random Walk가 아직도 이해하기 어렵네요. 추후에 다시 작성해서 올리겠습니다.

        public double CountRandomWalk(int m, int n)
        {

            var count = 0d;
            var enabled = new bool[m, n];
            var matrix = new int[m, n];
            var maxX = m - 1;
            var maxY = n - 1;
            var left = m*n;
            var random = new Random();
            var positionX = random.Next(0, m);
            var positionY = random.Next(0, n);

            while (true)
            {

                count++;
                matrix[positionX, positionY]++;
                if (!enabled[positionX, positionY])
                {
                    enabled[positionX, positionY] = true;
                    if (--left == 0) break;
                }

                if (positionX == 0) positionX += random.Next(0, 2);
                else if (positionX == maxX) positionX += random.Next(-1, 1);
                else positionX += random.Next(-1, 2);

                if (positionY == 0) positionY += random.Next(0, 2);
                else if (positionY == maxY) positionY += random.Next(-1, 1);
                else positionY += random.Next(-1, 2);

            }

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

늅늅입니다. 자바로 풀어봤습니다.

public static int sizeX;
    public static int sizeY;
    public static int mapCount;
    public static int moveCount;
    public static boolean[][] mapCheck;
    public static Random rand;
    public static int[] movePos;
    public static void main(String args[])
    {
        CreateMap(2000, 2000);
        Start();
    }

    public static void CreateMap(int x, int y)
    {
        sizeX = x; sizeY = y;

        mapCheck = new boolean[x][y];
        mapCount = x*y;
        moveCount = 0;
        movePos = new int[2];
        rand = new Random();

        for(int i = 0; i < x; i++) for(int j = 0; j <y; j++)
        {
            mapCheck[i][j] = false;
        }
    }

    public static void Start()
    {
        int moveX, moveY;

        moveX = 6; moveY = 5;

        mapCheck[moveX][moveY] = true;
        mapCount--;

        do 
        {
            movePos = RandMove(moveX, moveY);
            moveCount++;

            if(mapCheck[moveX][moveY] == false)
            {
                mapCheck[moveX][moveY] = true;
                mapCount--;
            }

            moveX = movePos[0];
            moveY = movePos[1];

            //System.out.println("바퀴가 " + moveX + ":" + moveY + "로 움직입니다." + " " + moveCount + " " + "아직 가보지 않은 방은 " + mapCount +"개 남았습니다."  );

        } while (mapCount != 0);

        Result();
    }

    public static int[] RandMove(int x, int y)
    {
        int moveTargetX, moveTargetY;

        moveTargetX = x;
        moveTargetY = y;

        int tempnum = rand.nextInt(3);
        switch(tempnum)
        {
        case 0:
            if(moveTargetX > 0)
                moveTargetX--;
            break;
        case 1:
            break;
        case 2:
            if(moveTargetX < sizeX-1)
                moveTargetX++;
            break;
        }

        tempnum = rand.nextInt(3);
        switch(tempnum)
        {
        case 0:
            if(moveTargetY > 0)
                moveTargetY--;
            break;
        case 1:
            break;
        case 2:
            if(moveTargetY < sizeY-1)
                moveTargetY++;
            break;
        }

        int[] targetPos = {moveTargetX, moveTargetY};

        movePos = targetPos;

        return movePos;
    }

    public static void Result()
    {
        System.out.println("바퀴가 움직인 횟수는 " + moveCount +"회 입니다.");
    }

제 컴퓨터에선 2000*2000 이 약 8~11초 정도 소요됩니다. 동선을 보기위해 주석을 푸니... ( ..)...

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

심화는 .... 어렵워서 ㅠㅠ .... 100 * 100하는데 꾀 걸림 ㅠㅠ.

stay : 108 , move : 287

Board

17 38 35 13 1

27 19 15 7 2

28 13 11 3 1

11 14 4 4 2

1 4 4 1 3 계속하려면 아무 키나 누르십시오 . . .

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


void move(int* x, int* y);
bool verdict(int** arr);

int h, w;
int stay;
void main() { 
    srand(time(NULL));

    int init_x =0, init_y = 0;
    int x, y;
    x = init_x;
    y = init_y;
    h=5;
    w=5;
    stay = 0;
    //arr[y][x];
    int** arr = (int**) malloc (sizeof(int*) * h);
    for(int i=0;i<h;i++)
        arr[i] = (int*) malloc (sizeof(int*) * w);

    for(int i=0;i<h;i++)
        for(int j=0;j<h;j++)
            arr[i][j] = 0;

    while(!verdict(arr)) {
        move(&x, &y);
        arr[y][x]++;
    }
    int sum = 9;
    for(int i=0;i<h;i++)
        for(int j=0;j<h;j++)
            sum = sum + arr[i][j];
    printf("stay : %d , sum : %d\n", stay, sum);

    printf("\n\nBoard\n");
    for(int i=0;i<h;i++){
        for(int j=0;j<h;j++) {
            printf("%d\t", arr[i][j]);
        }
        printf("\n");
    }

}

bool verdict(int** arr) {
    for(int i=0;i<h;i++)
        for(int j=0;j<h;j++)
            if(arr[i][j]==0)
                return false;
    return true;
}

void move(int* x, int* y) {
    int d = rand()%8;
    int sx = *x, sy = *y;
    switch(d) {
        case 1:
            if(*y-1 >=0 && *x-1>=0) {
                (*y)--;
                (*x)--;
            }
            break;
        case 2:
            if(*y-1 >=0) 
                (*y)--;
            break;
        case 3:
            if(*y-1 >=0 && *x+1<w) { 
                (*y)--;
                (*x)++;
            }
            break;
        case 4:
            if(*x-1 >=0) 
                (*x)--;
            break;
        case 5:
            if(*x+1<w)
                (*x)++;
            break;
        case 6:
            if(*x-1 >=0  && *y+1 < h) {
                (*y)++;
                (*x)--;
            }
            break;
        case 7:
            if(*y+1 < h)
                (*y)++;
            break;
        case 8:
            if(*y+1 < h && *x+1 < w) {
                (*y)++;
                (*x)++;
            }
            break;
    }
    if(sx==*x && sy==*y)
        stay++;
}

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

x, y, gps = input().split(' ')
x, y, gps = int(x), int(y), list(map(int,gps.split('.')))
_map = [0 for z in range(x*y)]
_list = [[a,b] for a in range(x) for b in range(y)]

while 0 in _map:
    a = random.randint(-1,1)
    b = random.randint(-1,1)
    if gps[0]+a == x or gps[0]+a < 0 or \
       gps[1]+b == y or gps[1]+b < 0:
        continue
    gps = [gps[0]+a,gps[1]+b]
    _map[_list.index(gps)] += 1
for a in [_map[a:a+x] for a in range(0,x*y,x)][::-1]:
    print(a)
print('총 움직인 횟수 : %d' % sum(_map))

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

```{.java} import java.util.Random;

public class Random_Walk { int size_x,size_y = 0; int ori_x,ori_y = 0; int count = 0; int[][] matrix; public Random_Walk(int a, int b,int x, int y){ size_x = a; size_y = b; ori_x = x; ori_y = y; matrix = new int[size_x][size_y]; } public void random_walk(){ Random random = new Random();

    while(count < size_x * size_y){
        switch(random.nextInt(8)){
            case 0 : 
                if(!check_this(ori_x, ori_y+1))
                    break;
                ori_y++; break;
            case 1:
                if(!check_this(ori_x+1, ori_y+1))
                    break;
                ori_x++;ori_y++; break;
            case 2: 
                if(!check_this(ori_x+1, ori_y))
                    break;
                ori_x++; break;
            case 3: 
                if(!check_this(ori_x+1, ori_y-1))
                    break;
                ori_x++;ori_y--; break;
            case 4: 
                if(!check_this(ori_x, ori_y-1))
                    break;
                ori_y--; break;
            case 5: 
                if(!check_this(ori_x-1, ori_y-1))
                    break;
                ori_x--;ori_y--; break;
            case 6: 
                if(!check_this(ori_x-1, ori_y))
                    break;
                ori_x--; break;
            case 7: 
                if(!check_this(ori_x-1, ori_y+1))
                    break;
                ori_x--;ori_y++; break;
        }
    }
}

public boolean check_this(int x, int y){
    if(0 > x | x >= size_x)
        return false;
    if(0 > y | y >= size_y)
        return false;

    if(matrix[x][y] == 0)
            count++;
    matrix[x][y]++;

    return true;

}

public void print_matrix(){
    for(int i = 0; i < size_x; i++){
        for(int j = 0; j < size_y; j++)
            System.out.print(matrix[i][j]+" ");
    System.out.println();
    }
}

}

```> 다른분들 풀이를 보니 저도 비슷하게 풀었더군요. matrix의 배열 하나하나를 0으로 체크하고 다 돌았나 확인하는 방법은 너무 느린거 같아서 count 변수를 따로 만들어 다 회전했나 확인하게 했습니다. 랜덤하게 움직이는 것은 Random class를 이용했습니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#-*- coding:utf-8 -*-
import numpy as np
import time
##입력 : 격자의 가로, 세로 크기, 바퀴벌레의 초기 위치            ##
##출력 : 각 칸에 바퀴벌레가 멈추었던 횟수, 바퀴벌레가 움직인 횟수. ##

def f_cocka(h,v,i,j):
    array = np.zeros((v,h),dtype=int)
    count = 0
    switch_case = {
        1: (0, -1), 2: (1, -1),
        3: (1,  0), 4: (1,  1),
        5: (0,  1), 6: (-1, 1),
        7: (-1, 0), 8: (-1,-1)
    }
    while len(array[array==0]) != 0:
        #랜덤으로 방향을 움직이고 그 전에 장소에 1를 더함
        direction = np.random.randint(1, 9)
        d_x = switch_case[direction][0]
        d_y = switch_case[direction][1]
        if ((i+d_x < 0)|(i+d_x >= v)|(j+d_y < 0)|(j+d_y >= h)):
            continue
        else :
            count += 1
            array[i, j] += 1
            i += d_x
            j += d_y
    return array,count

startTime = time.time()
print f_cocka(100,100,2,3)
endTime = time.time()
print "걸린 시간은 %.2f 초" % (endTime - startTime)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

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

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(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