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

2개의 풀이가 있습니다.

C# 입니다.

const int X = 100, Y = 100;
const int BOUNDX = X - 1, BOUNDY = Y - 1;        

bool[,] isPassPos = new bool[X, Y];
int[,] numPassPos = new int[X, Y];
int remainPosCount = X * Y;

Random rnd = new Random();
int posX = rnd.Next(0, X);
int posY = rnd.Next(0, Y);                        
double moveCount = 0;

while (true)
{
    moveCount++;
    numPassPos[posX, posY]++;

    if (!isPassPos[posX, posY])
    {
        isPassPos[posX, posY] = true;
        if (--remainPosCount == 0) break;
    }

    switch (posX)
    {
        case 0: posX += rnd.Next(0, 2); break;
        case BOUNDX: posX += rnd.Next(-1, 1); break;
        default: posX += rnd.Next(-1, 2); break;
    }
    switch (posY)
    {
        case 0: posY += rnd.Next(0, 2); break;
        case BOUNDY: posY += rnd.Next(-1, 1); break;
        default: posY += rnd.Next(-1, 2); break;
    }
}

Console.WriteLine("MoveCount : " + moveCount);

C#의 경우는 100 x 100을 실행하는데에는 20밀리초 정도가 걸립니다.C#의 기본 난수 발생은 Donald E. Knuth의 감산 알고리즘, 파이썬은 메르센 트위스터가 기본 알고리즘이라고 하네요. 아마 랜덤의 생성에서 대부분의 시간이 차이나는걸로 보입니다. 저도 단순 무식한 방법으로 했구요, 남아있는 위치의 카운트 변수를 추가적으로 만들어 마지막을 체크했습니다. 문제엔 꼭 다음 스텝에 이동을 해야한다는 조건이 없기때문에, 방향 백터가 0,0이 나오는 경우도 있습니다. 그래서 그 자리에 그대로 머물러 있는 경우도 카운트에 포함됩니다. 총 이동 카운트는 20 ~ 50만까지 다양하게 찍힙니다.

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

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

풀이 작성

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

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