Python 3.4 입니다. 좌표값을 사전으로 처리하는 방법을 사용하였습니다. 100*100 수행시 제 컴퓨터에서 약 1초 정도 소요되네요(36만번 이동)

import random
import itertools
import time

DIRECTION = list(itertools.product((-1, 0, 1), repeat=2))
DIRECTION.remove((0, 0))


def roach(xsize, ysize, xpos, ypos):
    matrix = {}
    pos = (xpos, ypos)
    count = 0
    while len(matrix) < xsize * ysize:
        matrix[pos] = matrix.get(pos, 0) + 1
        count += 1
        while True:
            tempdir = random.choice(DIRECTION)
            temppos = (pos[0] + tempdir[0], pos[1] + tempdir[1])
            if -1 < temppos[0] < xsize and -1 < temppos[1] < ysize: break
        pos = temppos
    return count, matrix

if __name__ == '__main__':
    t=time.time()
    xsize, ysize, xpos, ypos = 100, 100, 0, 0
    r= roach(xsize,ysize,xpos,ypos)
    print(r[0])
    print(time.time()-t)
    for i in range(ysize):
        print(' '.join(['{0:3}'.format(str(r[1][(j,i)])) for j in range(xsize)]))

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만까지 다양하게 찍힙니다.

제 PC에서는 100X100 크기일 때 약 2~4초대에 결과가 나옵니다. (시작위치는 랜덤으로 했습니다.)

다음 위치를 고를 때 딱 한 번의 랜덤연산을 하기위해서 현 위치에서 갈 수 있는 위치를 모두 뽑은 다음, 그 중 하나를 랜덤으로 선택합니다. (3 ~7 개 중에서 하나를 고릅니다.) 한 번도 방문하지 않은 칸의 수를 별도 변수로 두고, 최초 방문하는 방이 있을 때마다 이 값을 감소시켜서 이 값이 0보다 큰 동안만 루프를 돌게 했습니다.

그런데 1000 X 1000 크기일 때는 너무 느려서 뭔가 다른 방법이 필요할 듯 합니다.

from random import randrange

def nextPos(i, _w, _h):
    _x = i % _w
    _y = i // _w
    ofs = [(_x + x, _y + y) for x in (-1, 0, 1) for y in (-1, 0, 1)
           if x*2 + y != 0 and 0 <= (_x + x) < w and 0 <= (_y + y) < _h]
    rx, ry = ofs[randrange(len(ofs))]
    return ry * w + rx

w = 100
h = 100
sx = randrange(w)
sy = randrange(h)

def main():
    data = [0] * (h * w)
    s = h * w
    m = 0
    p = sy * w + sx

    while s > 0:
        if data[p] is 0:
            s -= 1
        data[p] += 1
        p = nextPos(p, w, h)
        m += 1

    # print result
    print('move: ', m)
    print('\n'.join([' '.join(["{:03d}".format(data[x + y * w]) for x in range(w)]) for y in range(h)]))

main()

파이썬 3.4 입니다. 심화문제는 나중에 생각해 봐야겠습니다. 100*100 격자만 되어도 많이 느려지네요. 많이 부족하지만 올려봅니다.

예를 들어, 격자의 가로는 3, 세로는 4 이고 초기 위치가 (2, 1) 라고 가정해 봅니다. 각 격자의 각 셀의 위치를 x,y 좌표를 기반으로 표시합니다. 각 위치에 해당하는 방문횟수를 stop_count 라는 리스트 형태로 작성해 보았습니다.

첫째로, 현재의 위치 정보 (2, 1) 을 받아들여 stop_count[1][0] 에 +1 을 합니다.

둘째로, 임의로 한칸 움직일 방향을 정합니다 (아래 코드의 __get_direction 함수). random 모듈의 randrange 를 이용하였고, x / y 축에 대해 각각 (-1, 0, 1) 사이의 값을 고르도록 했습니다. 단 위치에 따라 움직임에 제약생기는 부분을 고려하면, 위치 값이 1 인 경우는 (0, 1) 중에서, 최대값 ( x=3, or y=4 ) 이면 (-1, 0) 중에서 선택하도록 했습니다. 그리고, 선택한 값이 (0, 0) 이 되면 다시 선택하도록 했습니다.

셋째로, 움직임 방향이 정해지면 실제로 움직여서 새로운 위치정보를 얻습니다. 이때 움직인 횟수를 하나 더해줍니다. 그리고 다시 현재 위치 정보를 받아들여서 stop_count 리스트에 반영합니다.

이제, stop_count 리스트의 모든 값이 0 이 아닌지 확인합니다 (아래 코드의 __check_stop_by 함수). 만약 0이 있으면 전체 과정을 반복합니다.

아래는 Output 의 한 예 입니다.

The number of total movement is 36.

The matrix below is the number of visit to each cell.

1 3 3
2 4 3
1 5 5
2 4 4

from random import randrange

class RoachMatrix:
    def __init__(self,matrix_size,position):
        self.matrix_size = matrix_size
        self.x = self.matrix_size[0]; self.y =self.matrix_size[1]
        self.position = position
        self.stop_count = []
        for i in range(self.x):
            y_array = [0]*self.y
            self.stop_count.append(y_array)
        x = self.position[0]-1; y = self.position[1]-1
        self.stop_count[x][y] = 1
        self.all_stop_by = False
        self.total_move = 0

    def __get_direction(self):
        direction = [0,0]
        while direction == [0,0]:
            for i in range(2):
                if self.position[i] == 1: direction[i] = randrange(0,2)
                elif self.position[i] == self.matrix_size[i]: direction[i] = randrange(-1,1)
                else: direction[i] = randrange(-1,2)
        return direction

    def __check_stop_by(self):
        result = True
        for i in self.stop_count:
            if all(j for j in i) == False:
                result = False
                return result
        return result

    def record_move(self):
        while self.all_stop_by == False:
            direction = self.__get_direction()
            for i in range (2):
                self.position[i] = self.position[i] + direction[i]
            self.total_move += 1
            x = self.position[0]-1; y = self.position[1]-1
            self.stop_count[x][y] = self.stop_count[x][y] + 1
            self.all_stop_by = self.__check_stop_by()
        print("The number of total movement is %d.\n"%self.total_move)

    def print_stop_count(self):
        print("The matrix below is the number of visit to each cell.\n")  
        for i in range(self.y-1,-1,-1):
            line = ''
            for j in range(self.x):
                temp_count = str(self.stop_count[j][i])+'\t'
                line = line + temp_count
            print(line)            

matrix_size = [3,4]
start_pos = [2,1]

a = RoachMatrix(matrix_size,start_pos)
a.record_move()
a.print_stop_count()

public class RandomWalk {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int width = Integer.parseInt(sc.nextLine());
        int height = Integer.parseInt(sc.nextLine());
        int[][] map = new int[width][height];
        int count = 0;
        int remained = width * height;

        int curX = Integer.parseInt(sc.nextLine());
        int curY = Integer.parseInt(sc.nextLine());
        sc.close();

        long startTime = System.currentTimeMillis();
        while(true) {
            map[curX][curY]++;
            if(map[curX][curY] == 1) {
                remained--;
                if(remained == 0) {
                    break;
                }
            }

            Random random = new Random();
            while(true) {
                int preX = curX, preY = curY;
                int rand = random.nextInt(9);
                switch(rand) {
                case 1: preX--; preY--; break;
                case 2: preY--;         break;
                case 3: preX++; preY--; break;
                case 4: preX--;         break;
                case 5: preX++;         break;
                case 6: preX--; preY++; break;
                case 7: preY++;         break;
                case 8: preX++; preY++; break;
                }

                if(0 <= preX && preX < width && 0 <= preY && preY < height) {
                    curX = preX;
                    curY = preY;
                    break;
                }
            }

            count++;
        }
        long endTime = System.currentTimeMillis();

        System.out.println("elapsed time: " + (endTime - startTime));
        System.out.println("count: " + count);

        for(int i = 0; i < height; i++) {
            for(int j = 0; j < width; j++) {
                System.out.printf("%6d ", map[j][i]);
            }
            System.out.println();
        }
    }
}

walk = function(mat, row, col, n){
  mat[row,col]=mat[row,col]+1
  if(row>1 && row<nrow(mat)){    v.row=(row-1):(row+1)
  } else if(row>1) { v.row=(row-1):row
  } else if(row<nrow(mat)) { v.row=row:(row+1)
  } else {v.row=row}
  if(col>1 && col<ncol(mat)){ v.col=(col-1):(col+1)
  } else if(col>1) { v.col=(col-1):col
  } else if(col<ncol(mat)) { v.col=col:(col+1)
  } else {v.col=col}
  repeat{
    sample.row=sample(v.row, 1)
    sample.col=sample(v.col, 1)
    if(!((sample.row==row) && (sample.col==col))) {row<<-sample.row; col<<-sample.col; break} 
  }
  return(mat)
}
row=1
col=1
matt=matrix(0, 100, 100)
system.time(repeat{
    matt=walk(matt, row, col)
    if(all(matt>0)==T) {cat("완료\n") ; print(matt) ; print(sum(matt)); break}
  }
)

R로 무식하게 짜봤습니다.

모든 값이 0인 행렬을 생성하고 해당 위치에 바퀴벌레가 올 경우 +1을 해주며 모든 값이 0보다 클 경우 현재 행렬과 움직인 회수를 출력합니다. 바퀴벌레의 이동은 각 행과 열에 대해 if문으로 범위를 정하고 임의로 정하며 제자리에 있는 경우는 제외했습니다. 마지막으로 재귀함수를 통해 모든 칸이 채워질 때까지 반복했습니다.

만일 격자가 매우 클 경우 바퀴벌레의 이동횟수는 격자 크기에 대해서 기하급수적으로 증가하기 때문에 계산이 오래 걸리고 컴퓨터 사양에 많이 의존할 것 같네요.. 실제로 R 코드에서는 재귀 호출에 한계가 있는지 10x10 정도의 격자가 한계더군요.

수정: 코드가 지저분해 졌지만 재귀 호출을 하지 않도록 해보았습니다. 100x100격자에 34만번 이동이 90초 정도 걸리는 듯 합니다

system.time(repeat{
    matt=walk(matt, row, col)
    if(all(matt>0)==T) {cat("완료\n") ; print(matt) ; print(sum(matt)); break}
  }
)
[1] 346112
 사용자  시스템 elapsed 
  90.90    0.03   92.29 

지뢰찾기랑 거의 동일하게 만들었습니다.

바퀴를 스타트 지점에 위치시킨 후 0~7 까지의 랜덤한 수를 받아서 그 수에 해당되는 방향으로 계속 이동시키고 이동시킬 때마다 카운트를 올립니다. 그리고 카운트가 0 인 위치(Square)가 없을 때까지 계속 이동시킵니다. 바퀴가 모든 위치를 거쳤다면 그 결과를 출력시킵니다.

100 x 100 인 경우, 경우에 따라서 다르지만 제 PC에서는 421,503번 이동에 50초가량 걸리네요. 술취한 바퀴벌레는 무조건 랜덤이기 때문에 어떤식으로 최적화가 가능할지는 생각해 봐야겠습니다.

파이썬입니다.

# -*- coding: utf-8 -*-
import unittest
import random


class Square:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.value = 0

    def __str__(self):
        return "%s\t" % self.value


class Matrix:
    direction = [
        (-1,-1),(0,-1),(1,-1),
        (-1,0),(+1, 0),
        (-1,+1),(0,+1),(1,+1),
    ]
    def __init__(self, m, n):
        self.map = []
        for y in range(n):
            cols = []
            for x in range(m):
                square = Square(x, y)
                cols.append(square)
            self.map.append(cols)

    def getSquare(self, x, y):
        if 0 <= x < len(self.map[0]) and 0 <= y < len(self.map):
            return self.map[y][x]
        else:
            return None

    def isWalkAll(self):
        for row in self.map:
            for square in row:
                if square.value == 0: return False
        return True

    def getNextSquare(self, square):
        d = self.direction[random.randint(0,7)]
        next = self.getSquare(square.x+d[0], square.y+d[1])
        if not next: return self.getNextSquare(square)
        else: return next

    def start(self, x, y):
        square = self.getSquare(x, y)
        square.value += 1
        next = square
        while not self.isWalkAll():
            next = self.getNextSquare(next)
            next.value += 1

    def reveal(self):
        total = 0
        result = []
        for row in self.map:
            for square in row:
                result.append(str(square))
                total += square.value
            result.append("\n")
        return "".join(result).strip(), total


class RoachTest(unittest.TestCase):
    def test1(self):
        matrix = Matrix(4, 7)
        matrix.start(0, 0)
        m, total = matrix.reveal()
        print m
        print '-' * 70
        print "Total movement: %s" % total


if __name__ == "__main__":
    unittest.main()

Python 2.7.6

프래그래밍 초보입니다. 어떠한 피드백도 환영합니다.

# -*- coding: cp949 -*-

import random

class Result: # 결과 객체용 클래스
    tile = [] # 각 타일별 벌레가 멈추었던 횟수를 저장하는 2차원 배열
    count = 0 # 바퀴벌레가 총 움직인 횟수

def bug_run(m, n, cood):
    tile = [[0 for i in xrange(n)] for j in xrange(m)] # 타일별 멈춘 횟수 초기값 0으로 세팅하여 생성
    tile[cood[0]][cood[1]] = 1 # 일단 시작 위치에도 멈춘 횟수 1을 줌
    new_cood = [] # 편의상 임시 변수(벌레의 이동 후의 새로운 좌표를 나타냄)
    count = 0 # 총 이동 횟수 저장용 변수

    while 1:

        while 1:
            random_dx = random.choice((-1, 0, 1,))
            random_dy = random.choice((-1, 0, 1,))
            new_cood = [cood[0]+random_dx, cood[1]+random_dy] # 벌레를 랜덤 이동시킴

            if not(random_dx == 0 and random_dy == 0): # 랜덤 이동의 유효성을 평가
                if new_cood[0] > -1 and new_cood[0] < m and new_cood[1] > -1 and new_cood[1] < n:
                    count = count + 1
                    break # 유효한 이동이 나오면 랜덤화 중단

        cood = [new_cood[0], new_cood[1]] # 실제로 벌레를 이동 시킴
        tile[cood[0]][cood[1]] = tile[cood[0]][cood[1]] + 1 # 이동한 타일에 대하여 멈춘 횟수를 업데이트

        trigger = True # 루프 종료 조건용 변수

        for i in xrange(m):
            if 0 in tile[i]:
                trigger = False # 각 타일에 멈춘 횟수 0이 하나라도 있으면 종료 불가

        if trigger:
            break

    result = Result()
    result.tile = tile
    result.count = count

    return result

# 테스트

bug_test = bug_run(6, 6, [3, 3])

for i in bug_test.tile:
    print i

print "Total Count: %d" % (bug_test.count)

파이썬입니다~ 바퀴벌레의 위치는 랜덤으로 입력되도록 했습니다. 바퀴벌레 위치는 cock_map에 바퀴벌레가 이동하면서 머문 횟수는 stack_map에 기록했습니다. cnt는 바퀴벌레가 이동한 횟수입니다~

class Roach:
    def __init__(self,a,b):
        self.mp = [[0 for i in range(b)] for x in range(a)]
        self.a = a
        self.b = b # a,b,mp을 글로벌 변수로 지정

    def start(self):
        from random import choice
        from random import randrange
        import copy

        cock_map = self.mp
        stack_map = copy.deepcopy(cock_map) # 딥카피로 리스트 내부까지 카피
        cnt = 0  

        pin_a = randrange(0,self.a)
        pin_b = randrange(0,self.b)
        cock_map[pin_a][pin_b] = "*"
        stack_map[pin_a][pin_b] += 1

        cont = True
        while cont:
            lst = [-1,0,1]
            temp_a = 0
            temp_b = 0
            temp_a = pin_a + choice(lst)
            temp_b = pin_b + choice(lst)
            if temp_a < 0 or temp_a >= self.a or temp_b < 0 or temp_b >= self.b:
                continue
            else:
                cock_map[pin_a][pin_b] = 0
                pin_a = temp_a
                pin_b = temp_b
                cock_map[pin_a][pin_b] = "*"
                stack_map[pin_a][pin_b] += 1
                cnt += 1

            check = True
            for i in range(self.a):
                for j in range(self.b):
                    if stack_map[i][j] == 0: check = False
            if check == True: cont = False
        print cnt
        print stack_map # 기존의 a,b를 모두 글로벌 변수 self.a, self.b로 변환

ck = Roach(4,4)
ck.start()

제 PC에서 100*100 기준시 빠를때는 4~5초 정도 소요되고, 느릴때에는 100초 정도가 걸렸습니다.
매번 소요시간이 일정치 않은걸로 봤을때, 파이썬 기본 랜덤 모듈의 난수생성 방식과 다른
방법을 사용해야 할것같은데 아직 대안은 찾지 못했습니다. 파이썬의 기본 난수 생성 알고리즘이
Mersenne Twister 인걸로 알고있는데 다른 방식의 난수생성 알고리즘을 적용하면
좀더 빨라질지 모르겠습니다.

coding by python beginner

import random
import time

startTime = time.time()

w = 100; h = 100; pos = [0, 0]; moveCnt = 0
posCounter = [[0 for x in range(w)] for y in range(h)]
posCounter[pos[0]][pos[1]] += 1

def getMovablePos():
    movablePos = [
        [[-1, -1], [-1, 0], [-1, 1]],
        [[0, -1], False, [0, 1]],
        [[1, -1], [1, 0], [1, 1]]
    ]

    if pos[0] == 0:
        movablePos[0] = list([False])*3
    elif pos[0] == h-1:         
        movablePos[2] = list([False])*3

    if pos[1] == 0:
        for p in movablePos: p[0] = False
    elif pos[1] == w-1:
        for p in movablePos: p[2] = False

    rs = []
    for line in movablePos:
        for p in line:
            if p is not False: rs.append(p) 
    return rs


def randomWalk():
    movablePos = getMovablePos()
    movePos = movablePos[random.randrange(0, len(movablePos))]

    for i in range(2): pos[i] += movePos[i]
    posCounter[pos[0]][pos[1]] += 1 


def chkEnd():
    for i in range(len(posCounter)):
        for j in range(len(posCounter[0])):
            if posCounter[i][j] == 0: return False          
    return True

while True:
    if chkEnd(): break      
    randomWalk()
    moveCnt += 1

endTime = time.time()
print(posCounter, moveCnt, endTime - startTime)

% MATLAB
function [map, cnt] = solution(r, c, ini)

    % map : 각지점에서 바퀴벌레가 멈추었던 횟수
    % cnt : 총 움직인 횟수 (초기 자리는 제외)

    map = zeros(r,c);
    indexmap = reshape(1:r*c, size(map));
    map(ini) = 1;
    cnt = 0;
    H = ones(3,3); % conv kernel
    currPos = ini;

    while inf
        cnt = cnt+1; % 움직임을 카운팅

        % 한위치에서 움직일수있는 가능성 공간(가로 세로 대각)
        t = false(r,c);
        t(currPos) = true;
        possible = logical(conv2(double(t), H, 'same'));
        possible(currPos) = false;  % 제자리에 있는것은 불가능하다고 가정
        ind = indexmap(possible);
        % 랜덤으로 이동
        currPos = ind(randi([1,length(ind)],1));
        map(currPos) = map(currPos)+1; % 각위치에 몇번 지나간지에 대한 카운팅

        % 모든 칸을 지나가면 while문 종료
        if all(map(:) ~= 0)
            break;
        end
    end
end

    Sub Main()
        Dim input() As Integer = Array.ConvertAll(Split(Console.ReadLine, " "), Function(d As String) CInt(Val(d)))

        Dim size As New Size(input(0), input(1))
        Dim pt As New Point(input(2), input(3))

        Dim map(size.Width - 1)() As Integer

        For x As Integer = 0 To size.Width - 1
            map(x) = New Integer(size.Height - 1) {}
        Next

        Dim cnt As Integer = 0
        Do
            cnt += 1
            map(pt.X)(pt.Y) += 1

r:
            Randomize()
            Dim direc As Integer = CInt(Rnd() * 8)

            Select Case direc
                Case 0, 3, 5
                    If pt.X > 0 Then : pt.X -= 1 : Else : GoTo r : End If
                Case 1, 6

                Case 2, 4, 7
                    If pt.X < size.Width - 1 Then : pt.X += 1 : Else : GoTo r : End If
            End Select

            Select Case direc
                Case 0 To 2
                    If pt.Y > 0 Then : pt.Y -= 1 : Else : GoTo r : End If
                Case 3 To 4

                Case 5 To 7
                    If pt.Y < size.Height - 1 Then : pt.Y += 1 : Else : GoTo r : End If
            End Select

            If map.Where(Function(n() As Integer) n.Contains(0)).Count = 0 Then
                Exit Do
            End If
        Loop

        For y As Integer = 0 To size.Height - 1
            For x As Integer = 0 To size.Width - 1
                Console.Write(map(x)(y) & vbTab)
            Next
            Console.WriteLine()
        Next

        Console.WriteLine("이동 횟수: " & cnt)

        Console.ReadLine()
    End Sub

    static void exce38()
    {
        int x = 1000, y = 1000, cnt = 0,walk = 0; 
        Random rand = new Random();
        int[] roach = { rand.nextInt(x), rand.nextInt(y) };
        int[][] stage = new int[x][y];

        for(int i=0;i<x;i++)
        {
            for(int j=0;j<y;j++)
            {
                stage[i][j] = 0;
            }
            System.out.println();
        }

        stage[roach[0]][roach[1]]++;
        cnt++;

        while (cnt != x * y)
        {
            int direc = rand.nextInt(8);


            /*for (int i = 0; i < x; i++)
            {
                for (int j = 0; j < y; j++)
                {
                    if (i == roach[0] && j == roach[1])
                        System.out.printf("＠");
                    else
                    {
                        if (stage[i][j] == 0)
                            System.out.printf("□");
                        else
                            System.out.printf("■");
                    }
                }
                System.out.println();
            }
            System.out.println();
            System.out.println("--------------------");*/

            switch (direc)
            {
                case 0:
                    if (roach[0] < x - 1 && roach[1] > 0)
                    {
                        roach[0]++;
                        roach[1]--;
                        walk++;
                        if (stage[roach[0]][roach[1]] == 0)
                            cnt++;
                        stage[roach[0]][roach[1]]++;
                    }
                    break;
                case 1:
                    if (roach[0] < x - 1)
                    {
                        roach[0]++;
                        walk++;
                        if (stage[roach[0]][roach[1]] == 0)
                            cnt++;
                        stage[roach[0]][roach[1]]++;
                    }
                    break;
                case 2:
                    if (roach[0] < x - 1 && roach[1] < y - 1)
                    {
                        roach[0]++;
                        roach[1]++;
                        walk++;
                        if (stage[roach[0]][roach[1]] == 0)
                            cnt++;
                        stage[roach[0]][roach[1]]++;
                    }
                    break;
                case 3:
                    if (roach[1] < y - 1)
                    {
                        roach[1]++;
                        walk++;
                        if (stage[roach[0]][roach[1]] == 0)
                            cnt++;
                        stage[roach[0]][roach[1]]++;
                    }
                    break;
                case 4:
                    if (roach[0] > 0 && roach[1] < y - 1)
                    {
                        roach[0]--;
                        roach[1]++;
                        walk++;
                        if (stage[roach[0]][roach[1]] == 0)
                            cnt++;
                        stage[roach[0]][roach[1]]++;
                    }
                    break;
                case 5:
                    if (roach[0] > 0)
                    {
                        roach[0]--;
                        walk++;
                        if (stage[roach[0]][roach[1]] == 0)
                            cnt++;
                        stage[roach[0]][roach[1]]++;
                    }
                    break;
                case 6:
                    if (roach[0] > 0 && roach[1] > 0)
                    {
                        roach[0]--;
                        roach[1]--;
                        walk++;
                        if (stage[roach[0]][roach[1]] == 0)
                            cnt++;
                        stage[roach[0]][roach[1]]++;
                    }
                    break;
                case 7:
                    if (roach[1] > 0)
                    {
                        roach[1]--;
                        walk++;
                        if (stage[roach[0]][roach[1]] == 0)
                            cnt++;
                        stage[roach[0]][roach[1]]++;
                    }
                    break;
            }
        }
        System.out.printf("움직인 횟수 : %d번\n",walk);
        for(int i=0;i<x;i++)
        {
            System.out.printf("%3d : ",i);
            for(int j=0;j<y;j++)
            {
                System.out.printf("(%3d)",stage[i][j]);
            }
            System.out.println();
        }

    }

모든 구역을 다 순회하였는가 판정을 2차원구역배열을 전부 체크하게되면 저거만 해도 O(n^2)가 되서... 처음 구역에 도착한 횟수를 세는 변수를 하나 지정해서 해당 변수가 구역 가로x세로 만큼 되면 전부 순회한것으로 판단하였습니다. 100x100은 0.5초 미만이고 1000x1000은 2~3초 정도 걸리긴 한데 출력에 시간이 한참 걸리네요. 주석 안은 바퀴의 움직임을 가시적으로 표시하기 위해서 사용했던 코드입니다.

느려용.. ㅠㅠ

from random import randint
import operator

def randommove():
    while True:
        p = (randint(-1,1),randint(-1,1))
        if p != (0,0):
            return p;

def roachmove(curpos,width,height):
    while True:
        m = randommove()
        nextpos = tuple(map(operator.add, curpos, m))
        if (nextpos[0] < 0 or nextpos[0] >= width or nextpos[1] < 0 or nextpos[1] >= height) is False:
            return nextpos

def drinkroach(width,height,curpos):
    area = width * height
    areacount = 0
    movecount = 0
    Matrix = [[0 for x in range(width)] for x in range(height)] 

    while True:
        x = curpos[0]
        y = curpos[1]

        if Matrix[y][x] == 0:
            areacount += 1

        Matrix[y][x] += 1
        movecount += 1

        if areacount == area:
            print 'movecount:',movecount
            # print Matrix
            break

        curpos = roachmove(curpos,width,height)

drinkroach(1000,1000,(0,0))

#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.

알고리즘은 다들 쓰신거랑 같구요, 사이즈가 커지면 꽤 오래 걸리네요.심화문제는 더 생각해봐야겠어요

from random import choice
x_size = 100
y_size = 100
visited_aim = x_size*y_size
initx, inity = 5,5

def roach(x_size,y_size,initx,inity):
    (x,y)=(initx,inity)
    land=[[0]*x_size for i in range(y_size)]
    land[y][x] = 1; move=0; visited = 1
    while True:
        land[y][x] += 1
        dx,dy = choice([(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)])
        if not x+dx in range(x_size) or not y+dy in range(y_size):continue
        x+=dx;y+=dy
        land[y][x] += 1; move+=1
        if land[y][x] == 1:
            visited+=1
            if visited==visited_aim : break
    for line in land:
        for point in line:
            print "%4d"%point,
        print
    print "Total move: %d"%move

roach(x_size,y_size,initx,inity)

Ruby

require 'set'

def random_walk(x, y, pos, g=[*1..y].product([*1..x]))
  rest, grid = g.to_set, g.map {|k| [k, 0]}.to_h
  move = ->c,r { p=[rand(c-1..c+1),rand(r-1..r+1)] until p!=[c,r] && grid[p]; p}
  (pos = move[*pos]; grid[pos] += 1; rest.delete pos) until rest.empty?
  puts grid.values.each_slice(x).map {|_|_.map{|c|"%3d "%c}*""}, grid.values.sum
end

성능

# 100 x 100 화면출력 포함 : 1.5초. +-0.5초
Rehearsal -----------------------------------------------------
random walk :       1.200000   0.000000   1.200000 (  1.207901)
out to console :    0.010000   0.000000   0.010000 (  0.003795)
-------------------------------------------- total: 1.210000sec

                        user     system      total        real
random walk :       0.000000   0.000000   0.000000 (  0.000008)
out to console :    0.010000   0.000000   0.010000 (  0.003654)

Output

# 10x10 case
random_walk(10, 10, [5,5]) 
 1   2   2   6   5   9   6   4   9   4
 2   5   7   4  13   8  10   4   5   5
 2  10   5  11  10   9   7   4   4   3
 2   8   7   9  20  13   8   3   8   5
 4   8   7   8  21  13   9   7   5   5
 4  13  10  19  12  12  10   8   4   3
 8   9  14  11   9   6  10   8   6   3
 3   5   4   8  18  14  11  10   5   9
 2   9   9  19  16  20  16  18   9   7
 2   4   8  11  15  16  20  12  11   5
841

Python 2.7

100*100은 약 1초 소요됩니다.

import random
d = zip([-1,-1,-1,0,0,1,1,1], [-1,0,1,-1,1,-1,0,1])
def walk(m, n, start=(0,0)):
    walkmat = [[0]*m for i in xrange(n)]
    posx = start[0]
    posy = start[1]
    unvisited = {(x,y) for x in xrange(m) for y in xrange(n)}-{(posx,posy)}
    walkmat[posy][posx]+= 1
    count = 0
    while unvisited:
        try:
            dx, dy = random.choice(d)
            assert 0 <= posx+dx < m
            assert 0 <= posy+dy < n
        except:
            continue
        posx+= dx
        posy+= dy
        walkmat[posy][posx]+= 1
        unvisited-= {(posx,posy)}
        count+= 1
    for y in xrange(n):
        for x in xrange(m):
            print walkmat[y][x],
        print
    print count

파이썬3.4입니다. 알고리즘이나 성능은 생각조차 못하고, 일단 출력되는데까지 했습니다.
제 컴이 문제인지(아니라면 더 비극ㅜ) maximum recursion depth exceeded 에러가 뜨길래, sys.setrecursionlimit를 늘려주면 된다고해서 일단 import해봤구요.
100x100이 뭔가요? 50x50만 해도 뻗어버리네요 ㅜㅜ
차후 실력이 늘거나 생각좀 해보고 수정해봐야겠네요..

from random import *
from pprint import *
import sys
sys.setrecursionlimit(10000000)
def f(x, y, walk = 0):
    global mtx
    def chk():
        for i in range(col):
            for j in range(row):
                if mtx[i][j] == 0:
                    return False
        return True
    if chk():
        return walk
    else:
        mtx[x][y] += 1
        a = randrange(-1, 2)
        b = randrange(-1, 2)
        while  x + a < 0 or x + a >= len(mtx) or y + b <0 or y + b >= len(mtx[0]):
            a = randrange(-1, 2)
            b = randrange(-1, 2)
        return f(x + a, y + b, walk + 1)
col, row = 30, 30 
x, y = 2, 3
mtx = [[0 for i in range(col)] for j in range(row)]
walk = f(x, y)
pprint(mtx)
print('walk', walk)

혹시 리스트가 느릴까봐, 모두 튜플로 바꿨고, 매트릭스는 좌표값을 키로, 방문횟수는 값으로 하여 딕셔너리로 했어요
매트릭스 딕셔너리를 셋으로 복사하여 방문한 곳은 셋에서 제거를 하면서 셋이 모두 비워질때까지 순환합니다.
100 x 100은 대략 2초 내외로 나오고, 300 x 300 이상도 많이 느리네요

'''
매트릭스를 딕셔너리로 구현. 혹시 리스트보다 빠를까봐
매트릭스의 키를 셋으로 복사하여, 한번 방문한 곳은 셋에서 제거함
모든 구역을 다 갔다면 셋이 {} 비어있음
'''
from random import randrange
from time import time

def make_matrix(col, row):
    matrix = {}
    for i in range(row):
        for j in range(col):
            matrix.update({(i, j): 0})
    return matrix

def walk(x, y):
    global matrix, matrix_set
    matrix[x, y] += 1
    matrix_set -= {(x, y)} #색인
    while True:
        dir_sel = DIR[randrange(8)]
        dir_sel_x, dir_sel_y = dir_sel[0], dir_sel[1]
        new_x, new_y = x + dir_sel_x, y + dir_sel_y
        if new_x < 0 or new_x >= col or new_y < 0 or new_y >= row:
            continue
        else:
            break
    return new_x, new_y

def start(x, y):
    a = time()
    chk = 0 #움직인 횟수
    while True:
        x, y = walk(x, y) 
        chk += 1
        if not matrix_set: #모두 방문하였으면
            break
    print(chk)
    print(matrix)
    b = time()
    print('time: %.2f' % (b - a))


col, row = 100, 100 
matrix = make_matrix(col, row)
matrix_set = set(matrix.keys())
DIR = (
    (-1, -1), (0, -1), (1, -1),
    (-1, 0), (1, 0),
    (-1, 1), (0, 1), (1, 1),
)

x, y = randrange(col), randrange(row)
start(x, y)

import random as rd
class cursor():
    def __init__(self, li, y, x):
        self.li, self.y, self.x = li, y, x
        self.li[y][x] += 1
        self.total = 0
    def get_movable(self):
        result = {'up':0, 'left':0, 'right':0, 'down':0}
        if self.y + 1 <= len(self.li) - 1:
            result['up'] = 1
        if self.x - 1 >= 0:
            result['left'] = 1
        if self.x + 1 <= len(self.li[0]) - 1:
            result['right'] = 1
        if self.y - 1 >= 0:
            result['down'] = 1
        return result
    def __next__(self):
        while 1:
            moves = self.get_movable()
            dy = rd.randint(-moves['down'],moves['up'])
            dx = rd.randint(-moves['left'],moves['right'])
            if dy == dx == 0: continue
            self.y += dy
            self.x += dx
            self.li[self.y][self.x] += 1
            self.total += 1
            if any(any(x == 0 for x in y) for y in self.li):
                continue
            else:
                break
        return self.li, self.total
    def print(self):
        for y in self.li:
            for x in y:
                print(x, end = ' ')
            print()
        print('\ntotal : '+str(self.total))
while __name__ == '__main__':
    m, n = list(map(int, input('>>>').split()))
    x, y = list(map(int, input('>>>>>>').split()))
    mp = list(list(0 for x in range(m)) for y in range(n))
    c = cursor(mp, y, x)
    next(c)
    c.print()

100*100에서 꽤 걸리네요. 파이썬 3.5.1

# 파이썬 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)

1. 파이썬 3.x입니다.
2. 매회 방향을 구할 때, 현재 위치에 따라서 움직일 수 있는 방향을 제한하였습니다. 속도저하가 있다면 여기에 있지 않을까 생각이 듭니다.
3. 바퀴의 머문 횟수는 dictionary로 구현하였습니다. 가독성은 떨어지지만 좌표를 나타내었습니다.

# Random walk

import random

length = int(input('너비 입력 :'))
height = int(input('길이 입력 :'))
(x_n , y_n) = (int(input('초기위치(x좌표) :')), int(input('초기위치(y좌표) :')))
board = {(i,j):0 for i in range(length) for j in range(height)}
move = ()
num_of_moves = 0

def proper_directions(x_n,y_n): #네모 밖으로 나가면 안되니까
    directions = set([(-1,1),(-1,0),(-1,-1),(0,1),(0,-1),(1,1),(1,0),(1,-1)])
    if x_n == 0:
        directions = directions - set([(-1,1),(-1,0),(-1,-1)])
    elif x_n == length -1:
        directions = directions - set([(1,1),(1,0),(1,-1)])
    if y_n == 0:
        directions = directions - set([(-1,-1),(0,-1),(1,-1)])
    elif y_n == height -1:
        directions = directions - set([(-1,1),(0,1),(1,1)])
    return list(directions)

board[(x_n,y_n)]=1 #초기위치
while list(board.values()).count(0)>0: #모든칸에 바퀴가 한번 이상 갈 때까지

    move = random.choice(proper_directions(x_n,y_n)) 
    x_n += move[0]
    y_n += move[1]
    board[(x_n,y_n)] += 1
    num_of_moves += 1

print('바퀴의 이동 횟수 : {}'.format(num_of_moves))
print('각 칸에 바퀴가 머물렀던 횟수 : {}'.format(board))

// 바퀴벌레 - C#
using System;
namespace Roach
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Ready>>>");
            string input = Console.ReadLine();
            int x = int.Parse(input.Split(' ')[0]);
            int y = int.Parse(input.Split(' ')[1]);
            int inix = int.Parse(input.Split(' ')[2]);
            int iniy = int.Parse(input.Split(' ')[3]);
            long[,] board = new long[x, y];
            int posx = inix - 1, posy = iniy - 1;
            board[posx, posy]++;
            Random r = new Random();
            long counter = 0;
            while(true)
            {
                bool check = true;
                int tempx = r.Next(-1, 2);
                int tempy = r.Next(-1, 2);
                if (tempx + posx < 0 || tempx + posx >= x || tempy + posy < 0 || tempy + posy >= x)
                    continue;
                else
                    posx += tempx; posy += tempy;
                board[posx, posy]++; counter++;
                for (int i = 0; i < x; i++)
                    for (int j = 0; j < y; j++)
                        if (board[i, j] == 0)
                            check = false;
                if (check)
                    break;
            }
            for (int i = 0; i < y; i++)
            {
                for (int j = 0; j < x; j++)
                    Console.Write("{0} ", board[j, i]);
                Console.WriteLine();
            }
            Console.WriteLine("Move Rate = {0}", counter);
        }
    }
}

Python3

1차원으로 만들어 봤습니다. 딱히 더 빠르진 않은 거 같네요.

from random import choice
import time

X, Y, cx, cy = tuple(map(int, input().split()))  # zero-base
roach = cx * X + cy
visits = [0 for x in range(X * Y)]
dir = [-X-1, -X, -X+1, -1, 0, 1, X-1, X, X+1]
stime = time.time()

visits[roach] = 1
vcnt = X*Y - 1
nmove = 0
while vcnt:
    next = list(filter(lambda x: 0 <= x < X*Y, [roach+d for d in dir]))
    roach = choice(next)

    if not visits[roach]: vcnt -= 1
    visits[roach] += 1
    nmove += 1

for i in range(X): print(visits[i*X:(i+1)*X])
print(nmove)
print('%.2f sec' % (time.time() - stime))

import random
import numpy as np

def RW(A,B,pos):
    grid = []
    for b in range(B):
        grid.append([0 for a in range(A)])
    D = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
    a = pos[0]
    b = pos[1]

    while np.prod(grid) == 0:
        grid[b][a] += 1
        candid = []
        for d in D:
            if 0<=a+d[1]<A and 0<=b+d[0]<B:
                candid.append(d)
        c = candid[int(np.random.choice(len(candid)))]
        a += c[1]
        b += c[0]
    print(grid, np.sum(grid)-1)

A = 4
B = 8
pos = (int(np.random.choice(A,1)),int(np.random.choice(B,1)))

RW(A,B,pos)

package codingdojang;

import java.util.Random; import java.util.Scanner;

public class ex38 {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); // 세로 길이
    int m = sc.nextInt(); // 가로 길이
    int map[][] = new int[n][m];
    int x = sc.nextInt(); // 벌레의 x
    int y = sc.nextInt(); sc.nextLine(); // 벌레의 y

    roach r = new roach(x,y,n,m);
    map[x][y] = 1;
    int remain = n*m -1; // 한번도 안지나간 좌표의 수
    Random rd = new Random();

    System.out.println(remain);


    while(remain>0) {
    r.move(rd.nextInt(8));
    map[r.getX()][r.getY()]++;
        if(map[r.getX()][r.getY()] == 1) {
            remain--;
        }
    }

    System.out.println(remain);
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            System.out.print(map[i][j]+ " "); // 각 좌표별 지나간 횟수 출력
        }
        System.out.println();
    }
}

}

class roach{ private int x; private int y; private int maxX; private int maxY;

public roach(int x,int y,int maxX,int maxY) {
    this.x = x;
    this.y = y;
    this.maxX = maxX;
    this.maxY = maxY;
}

public void move(int sw) {
    switch(sw) {
    case 0:
        if(x>0)
        x = x-1;
        break;
    case 1:
        if(x<maxX-1)
        x = x+1;
        break;
    case 2:
        if(y>0)
        y = y-1;
        break;
    case 3:
        if(y<maxY-1)
        y = y+1;
        break;
    case 4:
        if(x>0&&y>0) {
        x = x-1;
        y = y-1;
        }
        break;
    case 5:
        if(x>0&&y<maxY-1) {
        x = x-1;
        y = y+1;
        }
        break;
    case 6:
        if(x<maxX-1&&y>0) {
        x = x+1;
        y = y-1;
        }
        break;
    case 7:
        if(x<maxX-1&&y<maxY-1) {
        x = x+1;
        y = y+1;
        }
        break;          
    default:
        break;
    }
}

public int getX() {
    return x;
}
public int getY() {
    return y;
}

}

투플러스님꺼 참고해서 풀었어요. 랜덤으로 방향을 정하는것 보다 iter을 사용한 랜덤 방향전환이 확실이 속도면에서 빠른거 같아요

import random
import time
import itertools
t = time.time()
r = 100
c = 100

board = dict()
total = 0

direction = list(itertools.product((-1, 0, 1), repeat=2))
direction.remove((0, 0))

# random starting point
x = random.randint(0, r - 1)
y = random.randint(0, c - 1)
board[(x, y)] = 1
while len(board) < r*c:
    tempx, tempy = random.choice(direction)
    x += tempx
    y += tempy
    if x < 0:
        x = 0
    elif x > c-1:
        x = c-1
    if y < 0:
        y = 0
    elif y > r-1:
        y = r-1

    board[(x,y)] = board.get((x, y), 0) + 1
    total += 1

print(time.time() - t)
print(total)
print(board)

Java 입니다.

import java.util.Random;

public class level_3_drunken_cockroach {

public static void main(String[] args) {

    int xmin = 0;
    int xmax = 4; // 최대 가로 길이.
    int ymin = 0;
    int ymax = 7; // 최대 세로 길이.
    int count = 0;

    int[][] box = new int[ymax][xmax]; // 2차원 배열 생성. (현재는 가로 4칸, 세로 7칸, 총 28칸.)

    Random randomGenerator = new Random(); // 랜덤 한 수 생성하는 명렁.
    int randomY = randomGenerator.nextInt(ymax); // 0 부터 6 까지 랜덤 수.
    int randomX = randomGenerator.nextInt(xmax); // 0 부터 3 까지 랜덤 수.

    for(int i = 0; i < ymax; i++) // 모든 칸에 0 을 입력함.
    {
        for(int j = 0; j < xmax; j++)
        {
            box[i][j] = 0;
        }
    }
    box[randomY][randomX] = 1; // 시작. 랜덤 위치에 바퀴벌레 뿅.

    while(true) // 무한 반복.
    {
        if(randomY == ymin && randomX == xmin) // 시작점이 (최솟값, 최솟값) 이면.
        {
            randomY = randomGenerator.nextInt(2); // y 값이 0 이면, 0 ~ 1 까지 랜덤 수.
            randomX = randomGenerator.nextInt(2); // x 값이 0 이면, 0 ~ 1 까지 랜덤 수.
            box[randomY][randomX]++;
            count++;
        }
        else if(randomY == ymax - 1 && randomX == xmax - 1) // 시작점이 (최댓값, 최댓값) 이면.
        {
            randomY = randomGenerator.nextInt(2) + randomY - 1;
            randomX = randomGenerator.nextInt(2) + randomX - 1;
            box[randomY][randomX]++;
            count++;
        }
        else if(randomY == ymin && randomX == xmax - 1) // 시작점이 오른쪽 위 꼭지점 이면.
        {
            randomY = randomGenerator.nextInt(2) + randomY;
            randomX = randomGenerator.nextInt(2) + randomX - 1;
            box[randomY][randomX]++;
            count++;
        }
        else if(randomY == ymax - 1 && randomX == xmin) // 시작점이 왼쪽 아래 꼭지점 이면.
        {
            randomY = randomGenerator.nextInt(2) + randomY - 1;
            randomX = randomGenerator.nextInt(2) + randomX;
            box[randomY][randomX]++;
            count++;
        }
        else if(randomY == ymin && (randomX > xmin && randomX < xmax)) // 꼭지점을 제외한, 위 모서리.
        {
            randomY = randomGenerator.nextInt(2);
            randomX = randomGenerator.nextInt(3) + randomX - 1;
            box[randomY][randomX]++;
            count++;
        }
        else if(randomY == ymax - 1 && (randomX > xmin && randomX < xmax)) // 꼭지점을 제외한, 아래 모서리.
        {
            randomY = randomGenerator.nextInt(2) + randomY - 1;
            randomX = randomGenerator.nextInt(3) + randomX - 1;
            box[randomY][randomX]++;
            count++;
        }
        else if((randomY > ymin && randomY < ymax) && randomX == xmin) // 꼭지점을 제외한, 왼쪽 모서리.
        {
            randomY = randomGenerator.nextInt(3) + randomY - 1;
            randomX = randomGenerator.nextInt(2);
            box[randomY][randomX]++;
            count++;
        }
        else if((randomY > ymin && randomY < ymax) && randomX == xmax - 1) // 꼭지점을 제외한, 오른쪽 모서리.
        {
            randomY = randomGenerator.nextInt(3) + randomY - 1;
            randomX = randomGenerator.nextInt(2) + randomX - 1;
            box[randomY][randomX]++;
            count++;
        }
        else // 모서리 부분을 제외한 부분이면.
        {
            randomY = randomGenerator.nextInt(3) + randomX - 1;
            randomX = randomGenerator.nextInt(3) + randomX - 1;
            box[randomY][randomX]++;
            count++;
        }
        int judge = box[randomY][randomX]; // 모든 배열 요소 값이 1 이상일 경우 무한루프를 멈추게 할때 쓰일 변수.
        for(int i = 0; i < ymax; i++) // 모든 값들이 곱해준다.
        {
            for(int j = 0; j < xmax; j++)
            {
                judge = judge * box[i][j];
            }
        }
        if(judge != 0) // 모든 값들을 곱했을때 0이 아니면 무한루프 종료.
        {
            break;
        }
    }       
    for(int j = 0; j < ymax; j++) // o
    {
        System.out.println();
        for(int h = 0; h < xmax; h++)
        {
            System.out.print(box[j][h] + "  ");
        }
    }
    System.out.println();
    System.out.println("바퀴벌레가 돌아다닌 횟수 : " + count);
}

}

5일차만에 바퀴벌레를 잡긴했는데... 바퀴벌레 움직임이 이상하네요. 사각형 격자의 왼쪽위 꼭지점에서 오른쪽 아래 꼭지점으로 거의 이렇게 대각선 모양으로 움직이네요. 자바 초보라서 왜이러는지 잘 모르겠어요 검색해도 안나오고, 시드문제는 아닌거같고. 혹시 댓글로 조언해주시면 매우 감사하겠습니다. 애착가는 문제네요.

범위지정 난수로 문제를 풀었습니다.

파이썬 3.6

"""
아이디어>
 1. [column][row] 크기의 격자를 모든 요소값을 0으로 대입하여 만들고,
 2. 바퀴벌레 위치에 따른 이동 가능 방향 =>[좌상,상,우상,좌,우,좌하,하,우하]
 3. 현재 위치에서 위의 방향 리스트의 좌표값을 임의로 선택합니다. 이때 좌표값이 0<= x <= row-1, 0 <= y < column-1 범위 안에 있을때까지 임의 선택을 반복합니다. 
 4. 조건을 만족하는 자표값 이 선택되면 이동하고, 최초 시작위치에서 이동시 마다 이동횟수와 해당 좌표의 요소값을 1씩 증가 시킵니다.
 5. 매 이동시 모든 요소값에 대해 0 이 있는지 확인하여, 0 이 없을 때까지 이동을 계속합니다.
"""

import random

def random_walk(m,n,p):
    move,chk,tmp,x,y = 0, 0,[],p[0],p[1]
    matrix = [[0 for h in range(m)] for i in range(n)]
    while True:
        chk = 0
        direction = [[x-1,y-1],[x,y-1],[x+1,y-1],[x-1,y],[x+1,y],[x-1,y+1],[x,y+1],[x+1,y+1]]
        while True:
            tmp = random.choice(direction)
            if 0 <= tmp[1] <= n-1 and 0 <= tmp[0] <= m-1:
                break
        matrix[tmp[1]][tmp[0]] += 1
        move += 1        
        for arr in matrix:
            if 0 in arr:
                chk += 1
        if chk == 0:
            break
        x,y = tmp[0],tmp[1]        
    for i in matrix:
        print(''.join([str("{0:^4}".format(h)) for h in i]))
    print("\n""☞이동한 횟수 = %d"% move)

if __name__ == "__main__":
    m = int(input("row = "))
    n = int(input("column = "))
    p = [int(input("x(0 <= y <= row-1) = ")),int(input("y(0 <= y <= column-1) = "))]
    print("\n")
    random_walk(m,n,p)

*결과값

row = 4
column = 2
x(0 <= y <= row-1) = 1
y(0 <= y <= column-1) = 1


 3   8   7   1  
 2   5   2   1  

☞이동한 횟수 = 29

row = 9
column = 5
x(0 <= y <= row-1) = 3
y(0 <= y <= column-1) = 3


 5   2   3   9   13  16  11  6   3  
 8   9   8   18  25  20  11  9   6  
 7   8   7   12  13  14  9   12  4  
 4   6   5   8   8   12  11  7   5  
 1   3   6   4   5   7   6   5   3  

☞이동한 횟수 = 374

import random
def randomwalk(m,n,a,b):
    l = [[0 for i in range(m)] for j in range(n)]
    l[b][a] = 1
    notpassed = m*n-1
    while notpassed:
        if a == 0 and b == 0:
            x = random.choice([(1,0), (1,1), (0, 1)])
        elif a == 0 and b == n-1:
            x = random.choice([(0, -1), (1, -1), (1, 0)])
        elif a == m-1 and b == 0:
            x = random.choice([(0, 1), (-1, 1), (-1, 0)])
        elif a == m-1 and b == n-1:
            x = random.choice([(0, -1), (-1, 0), (-1, -1)])
        elif  a == 0:
            x = random.choice([(0, -1), (1, -1), (1, 0), (1, 1), (0, 1)])
        elif a == m-1:
            x = random.choice([(0, -1), (0, 1), (-1, 1), (-1, 0), (-1, -1)])
        elif b == 0:
            x = random.choice([(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0)])
        elif b == n-1:
            x = random.choice([(0, -1), (1, -1), (1, 0), (-1, 0), (-1, -1)])
        else:
            x = random.choice([(0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1)])
        a += x[0]
        b += x[1]
        if l[b][a] == 0:
            notpassed -= 1
        l[b][a] += 1
    return l
a = list(map(int, input().split(' ')))
b = randomwalk(a[0], a[1], a[2], a[3])
result = 0
for i in b:
    print(i)
    result += sum(i)
print(result - 1)

생각보다 좀 많이 움직이네요. 그래도 모두 채웠을때 출력이 됩니다.

using System;

namespace CSharp_Test
{
    class Program
    {
        static void Main(string[] args)
        {
            int width;
            int height;

            int pos_x, pos_y; //바퀴벌래 위치
            int[,] arr;

            Console.Write("width : "); width = int.Parse(Console.ReadLine());
            Console.Write("height : "); height = int.Parse(Console.ReadLine());
            Console.Write("pos_x : "); pos_x = int.Parse(Console.ReadLine());
            Console.Write("pos_y : "); pos_y = int.Parse(Console.ReadLine());

            arr = new int[height, width];

            arr[pos_y, pos_x]++;
            bool flag = true;

            int moveCount = 0; //바퀴벌레 이동횟수

            //처음 배열(위치)
            for (int i = 0; i < height; i++)
            {
                for (int j = 0; j < width; j++)
                {
                    Console.Write("{0} ", arr[i, j]);
                }
                Console.WriteLine();
            }

            while (true)
            {
                int count = 0;

                //바퀴벌레 이동
                moveCount++;
                Random r = new Random();

                int randomNum;

                while(true)
                {
                    bool s = false; //움직여도 되는 위치로 선정되면 true로 빠져나간다.

                    randomNum = r.Next(1, 5);

                    if (width - 1 == pos_x && randomNum == 1)//x마지막에 있는경우
                        continue;
                    if (pos_x == 0 && randomNum == 2)          //x맨앞에 있는 경우
                        continue;
                    if (height - 1 == pos_y && randomNum == 3) //y마지막에 있는 경우
                        continue;
                    if (pos_y == 0 && randomNum == 4)//y맨앞에 있는 경우
                        continue;
                    break;
                }

                switch (randomNum)
                {
                    case 1://우
                        pos_x++;
                        arr[pos_y, pos_x]++;
                        break;
                    case 2://좌
                        pos_x--;
                        arr[pos_y, pos_x]++;
                        break;
                    case 3://상
                        pos_y++;
                        arr[pos_y, pos_x]++;
                        break;
                    case 4://하
                        pos_y--;
                        arr[pos_y, pos_x]++;
                        break;
                }

                //검사
                for (int i = 0; i < height; i++)
                {
                    for (int j = 0; j < width; j++)
                    {
                        if (arr[i, j] == 0)
                        {
                            count++;
                        }
                    }
                }
                //모든 지역을 들렀다면 끝
                if (count == 0)
                    break;
            }
            Console.WriteLine("moveCount : {0}", moveCount);
            Console.WriteLine();

            //배열출력 (지역마다 들럿던 횟수)
            for (int i = 0; i < height; i++)
            {
                for (int j = 0; j < width; j++)
                {
                    Console.Write("{0} ", arr[i, j]);
                }
                Console.WriteLine();
            }
        }
    }
}

import java.util.Random;
import java.util.Scanner;

public class Table {


    static int verticals = 0;

    static int rows = 0;

    public static void execute(int[][] table, int count, int row, int vertical){
        if(table[row][vertical] == 0){
            count--;
            table[row][vertical]++;
        }else{
            table[row][vertical]++;
        }
        if(count == 0){
            return ;
        }

        Random random = new Random();

        boolean flag = false;

        while(!flag){
            int direction = random.nextInt(4);

            if(direction == 0){
                if(row-1 >= 0){
                    row--;
                    flag = true;
                }
            }else if(direction == 1){
                if(vertical+1 < verticals){
                    vertical++;
                    flag = true;
                }

            }else if(direction == 2){
                if(row +1 < rows){
                    row++;
                    flag = true;
                }


            }else{
                if(vertical-1 >= 0){
                    vertical--;
                    flag = true;
                }

            }

        }
        execute(table, count, row, vertical);

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);

        verticals = sc.nextInt();
        rows = sc.nextInt();
        int startRow = sc.nextInt();
        int startVertical = sc.nextInt();

        int[][] table = new int[rows][verticals];

        int count = rows * verticals; // 모든 칸수

        execute(table, count, startRow, startVertical);


        int sum = 0;
        for(int i=0; i< table.length; i++){
            for(int j=0; j < table[i].length; j++){
                System.out.printf("%3d" , table[i][j]);
                sum += table[i][j];

            }
            System.out.println();
        }
        System.out.println("sum :: " + sum);


    }

}

Swift입니다.

무작위로 이동하며, 최초 방문 타일의 갯수가 전체 타일 갯수와 같아지면 종료합니다. 엄청나게 큰 지도의 경우, 무작위라는 조건이 달려 있을 때 무엇을 할 수 있는지는 잘 모르겠습니다.

지도 크기가 1000x1000인 경우 약 40초에 방문한 타일 갯수는 약 7천만개입니다.

// Random Walk
import Foundation

let width = 100     // <-- Change this!!
let height = 100    // <-- Change this!!

let totalTileCount = width * height
var map = Array(repeating: Array(repeating: 0, count: width), count: height)
var foundNewTileCount = 0
var x = 0
var y = 0

while true {
    if map[y][x] == 0 {
        foundNewTileCount += 1
        print("Found tile count -> \(foundNewTileCount)")
    }
    map[y][x] += 1

    if foundNewTileCount < totalTileCount {
        let direction = Int(arc4random_uniform(8))
        if direction == 0 || direction == 1 || direction == 7 { // y - UP
            y = y > 0 ? (y - 1) : (y + 1)
        }
        if direction == 3 || direction == 4 || direction == 5 { // y - Down
            y = y < (height - 1) ? (y + 1) : (y - 1)
        }
        if direction == 1 || direction == 2 || direction == 3 { // x - Right
            x = x < (width - 1) ? (x + 1) : (x - 1)
        }
        if direction == 5 || direction == 6 || direction == 7 { // x - Left
            x = x > 0 ? (x - 1) : (x + 1)
        }
    } else {
        break
    }
}

var total = 0
for line in map {
    total += line.reduce(0, +)
}
print("Total move count -> \(total)")

파이썬입니다. 100*100 크기 실행이 1초정도 걸리네요

from random import *

w=int(input('가로길이 입력:'))
h=int(input('세로길이 입력:'))
loc=list(int(input('바퀴벌레의 초기위치 입력:')) for i in range(2))
mylist=[ [0 for n in range(w)] for m in range(h)]
mylist[loc[0]][loc[1]]+=1
count=0
zero=1
while True:
    i,j=randint(-1,1),randint(-1,1)
    if loc[0]+i<0 or loc[1]+j<0 or loc[0]+i>h-1 or loc[1]+j>w-1:
        continue
    loc[0]+=i
    loc[1]+=j
    if mylist[loc[0]][loc[1]]==0:
        zero+=1
    mylist[loc[0]][loc[1]]+=1
    count+=1
    if zero==w*h:
        break
for myli in mylist:
    print(myli)
print(count)

def random_walk(x, y, startx, starty):
    import random
    board = [[0 for xa in range(x)] for ya in range(y)]
    board[starty][startx] = 1
    xaxis = startx - 1
    yaxis = starty - 1
    direction = 0
    check = 0
    dilist = list(range(1, 9))
    moving = 0
    while not check:
        direction = dilist.pop(dilist.index(random.choice(dilist)))
        if direction == 1: xaxis -= 1; yaxis -= 1
        elif direction == 2: yaxis -= 1
        elif direction == 3: xaxis += 1; yaxis -= 1
        elif direction == 4: xaxis -= 1
        elif direction == 5: xaxis += 1
        elif direction == 6: xaxis -= 1; yaxis += 1
        elif direction == 7: yaxis += 1
        else: xaxis += 1; yaxis += 1
        try: board[yaxis][xaxis] += 1
        except: continue
        else:
            dilist = list(range(1, 9))
            moving += 1
            for i in board:
                if 0 in i:
                    break
                check += 1
            if check != len(board):
                check = 0
    board.append(moving)
    return board
for run in random_walk(100, 100, 2, 3):
    print(run)

Python 3입니다

board변수는 이름 그대로 바퀴벌레가 움직이는 판이며

xaxis변수로 x좌표를, yaxis변수로 y좌표를 컨트롤합니다

direction변수로 좌상, 상, 우상, 좌, 우, 좌하, 하, 우하 8가지의 움직이는 경우 중 하나를 택한 뒤

board리스트를 벗어나면 방향을 다시 설정하여 움직이는 방식입니다

짧게 짜봤습니다. 잘 돌아가네요 ㅎㅎ

import numpy as np
import random as rd

n, m = list(map(int, input('n, m = :').split()))
field = np.zeros((n, m))
start = divmod(rd.choice(range(n * m)), m)
count = -1
while True:
    point = start
    px, py = point
    field[start] += 1
    count += 1
    if 0 not in field: break
    while True:
        dx = rd.choice([-1, 0, 1])
        dy = rd.choice([-1, 0, 1])
        if (dx, dy) != (0, 0) and 0 <= px + dx < m and 0 <= py + dy < n: break
    next_point = (px+dx, py+dy)
    start = next_point

print(field, '\n\n', count)

결과

n, m = : 100 100
[[ 4. 10.  9. ... 17. 10.  5.]
 [11. 13. 14. ... 30. 12.  8.]
 [14. 16. 14. ... 22. 19.  4.]
 ...
 [20. 37. 45. ... 39. 39. 28.]
 [35. 51. 52. ... 38. 31. 24.]
 [19. 43. 37. ... 24. 24. 11.]] 

 292178

파이썬 3

• numpy 사용하였습니다.

• 바퀴벌레가 움질일 수 있는 옵션을 계산하는 부분은 다른 코드들과 차별됩니다.

import numpy as np
import random

row, col, (r0,c0) = 7, 4, (3,0) #입력값: 행, 열, 시작 좌표
grid = np.zeros((row,col))
grid[r0,c0] = 1
print(grid)

count = 0
r, c = r0, c0
while True:
    rc_options = [(i, j) for i in range(max(r-1, 0), min(r+1, row-1) + 1) for j in range(max(c-1, 0), min(c+1, col-1) + 1)]
    r_temp, c_temp = random.choice(rc_options)
    if r_temp == r and c_temp == c: #움직이지 않은 경우
        continue
    else:
        r, c = r_temp, c_temp
    count += 1
    grid[r, c] += 1

    if np.count_nonzero(grid==0) == 0: #모든 곳을 다 가봤다면
        break

print("이동횟수: {}".format(count))
print(grid)

결과

이동횟수: 204
[[ 4.  1.  1.  1.]
 [ 6.  4.  3.  3.]
 [ 5. 13.  7.  9.]
 [13. 10. 11. 11.]
 [11. 16.  8.  5.]
 [ 4. 10. 15.  4.]
 [ 6. 14.  7.  3.]]

'''
매번 zero 가 아닌 것을 모두 체크할 필요는 없고, 1 이 되는 순간 done_count 를 하나씩 올리면
이 갯수가 가로x세로 값과 같은 순간이 모두 1 이상이 되는 시점이겠죠.
'''

import random as rd
import numpy as np

h,v = map(int,input().split())

m = np.zeros((h,v),dtype=int)
x = rd.randint(1,h)
y = rd.randint(1,v)

walk_count = 0
done_count = 0

while 1:
    if x == 0: movex = rd.randint(0,1)
    elif x == (h-1): movex = rd.randint(-1,0)
    else: movex = rd.randint(-1,1)

    if y == 0: movey = rd.randint(0,1)
    elif y == (v-1): movey = rd.randint(-1,0)
    else: movey = rd.randint(-1,1)

    if (movex,movey) == (0,0):
        continue

    x = x + movex
    y = y + movey

    m[x,y] += 1
    walk_count += 1

    if m[x,y] == 1:
        done_count += 1
    if done_count == (h*v):
        break

print(walk_count)

from random import *

row,clm = map(int,input().split())

board = [0 for i in range(row*clm)]
dirc = ((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))

start = randint(0,row*clm-1)
board[start],cnt,cnt2 = 1,0,1

curps = start
while cnt2 < row*clm:
    d = dirc[randint(0,7)]
    if not(0<=curps//clm+d[0]<row and 0<=curps%clm+d[1]<clm): continue
    curps = (curps//clm+d[0])*clm+curps%clm+d[1]
    board[curps] += 1
    if board[curps] == 1: cnt2 += 1
    cnt += 1

for i in range(row*clm):
    print('{:{}}'.format(board[i],len(str(row*clm))),end=' ')
    if (i+1)%clm == 0: print()
print('\n',cnt)

import java.util.Random;
import java.util.Scanner;

public class main3 {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int count = 0;
        int check = 0;
        Random random = new Random();
        int move = 0;

        try {
            System.out.println("가로크기를 입력해 주세요.");
            int x = scn.nextInt();
            int bugX = x / 2;
            System.out.println("세로크기를 입력해 주세요.");
            int y = scn.nextInt();
            int bugY = y / 2;

            int[][] map = new int[x][y];
            map[bugX][bugY]++;

            while(true){
                move = random.nextInt(8);

                switch (move) {
                case 0:
                    bugX--;
                    bugY--;
                    break;
                case 1:
                    bugX--;
                    break;
                case 2:
                    bugX--;
                    bugY++;
                    break;
                case 3:
                    bugX--;
                    break;
                case 4:
                    bugX++;
                    break;
                case 5:
                    bugX--;
                    bugY++;
                    break;
                case 6:
                    bugY++;
                    break;
                case 7:
                    bugX++;
                    bugY++;
                    break;
                default:
                    break;
                }

                if(bugX < 0){
                    bugX++;
                }
                if(bugX >= x){
                    bugX--;
                }

                if(bugY < 0){
                    bugY++;
                }
                if(bugY >= y){
                    bugY--;
                }

                map[bugX][bugY]++;

                check = 0;
                for(int i = 0; i < x; i++){
                    for(int j = 0; j < y; j++){
                        if(map[i][j] > 0){
                            check++;
                        }
                    }
                }

                if(check >= (x * y)){
                    break;
                }
                count++;
            }
            for(int i = 0; i < x; i++){
                for(int j = 0; j < y; j++){
                    System.out.print("[" + map[i][j] + "] ");
                }
                System.out.println("");
            }
            System.out.println(count + "번 움직였습니다.");
        } catch (Exception e) {
            // TODO: handle exception
            e.printStackTrace();
        }

    }
}

씨 언어 로 풀었습니다. 바퀴벌레가 움직이지 않은 부분은 0. 움직이면 1로 고정. 멈추는 부분 마다 + 시켜서 얼마나 멈추는지 확인 바퀴벌레가 움직이는 방향을 -1, 0, 1 로 설정. 0 0 이 나오면 안움직이고 가만히 멍때린다고 가정. 임의의 자리도 그냥 랜덤 상수로 주었습니다.

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

int movingX()
{
    int moveX = (rand() % 3) -1;            //create -1 ~ 1;
    return moveX;
}

int movingY()
{
    int moveY = (rand() % 3) -1;            //create -1 ~ 1;
    return moveY;
}

int main()
{
    int x, y;
    scanf("%d %d", &x, &y);

    //Origin two dimesional array
    int **ptr = malloc(sizeof(int *)*x);

    for(int i = 0; i < x; i++)
    {
        ptr[i] = malloc(sizeof(int)*y);
    }

    //initialize
    for(int i = 0; i < x; i++)
    {
        for(int j = 0; j < y; j++)
        {
            ptr[i][j] = 0;
        }
    }

    //Temporary one
    int **Tptr = malloc(sizeof(int *)*x);

    for(int i = 0; i < x; i++)
    {
        Tptr[i] = malloc(sizeof(int)*y);
    }

    //initialize
    for(int i = 0; i < x; i++)
    {
        for(int j = 0; j < y; j++)
        {
            Tptr[i][j] = 0;
        }
    }



    srand(time(NULL));          //여러 난수로 나오게끔

    int tmpX = rand() % x ;     //0~x-1 create random num
    int tmpY = rand() % y ;     //0~y-1 create random num

    ptr[tmpX][tmpY] = 1;            //Create CockRoach

    printf("first C R location : %d %d\n", tmpX, tmpY);

    // moving there 

    int exitCount = 1;
    int moveCount = 0;
    int moveX = tmpX, moveY = tmpY;     //시작위치 임의의점에서 새로 시작
    int i = 0;                                      //얼마나 움직이는 지 확인 

    while( exitCount != x*y )
    {
        moveX += movingX();
        moveY += movingY();
        i++;

        //num X check
        if( moveX < 0)
        {
            ++moveX;
        }
        else if( moveX > x-1)
        {
            --moveX;
        }
        //num Y check
        if( moveY < 0 )
        {
            ++moveY;
        }
        else if( moveY > y-1)
        {
            --moveY;
        }

        Tptr[moveX][moveY] += 1;

        //moving check
        if( ptr[moveX][moveY] == 0)
        {
            printf("%d location %d , %d\n", ++moveCount, moveX, moveY);
            ptr[moveX][moveY] = 1;
            exitCount ++;
        }
    }

    printf("times C.R moved : %d\n", i);

    for(int v = 0; v < x; v++)
    {
        for(int k = 0; k < y; k++)
        {
            printf("%4d", Tptr[v][k]);
        }
        printf("\n");
    }
   free 해주세요 전 귀찮;
}

6 4
first C R location : 3 2
1 location 4 , 3
2 location 3 , 3
3 location 2 , 3
4 location 1 , 3
5 location 0 , 3
6 location 1 , 2
7 location 0 , 2
8 location 1 , 1
9 location 2 , 1
10 location 3 , 0
11 location 2 , 0
12 location 3 , 1
13 location 5 , 3
14 location 5 , 2
15 location 2 , 2
16 location 0 , 0
17 location 0 , 1
18 location 4 , 2
19 location 4 , 1
20 location 4 , 0
21 location 5 , 1
22 location 5 , 0
23 location 1 , 0
times C.R moved : 140
   9   6   3   2
   1   6   5   3
   3   8   7   5
   8   7   4   7
   6   3   4  12

import random as rd
def move(y,x,y_length,x_length):
    direction_t =  set([1,2,3,4,5,6,7,8])
    if y <= 0:
        direction_t -= set([1,2,3])
    if y >= (y_length-1):
        direction_t -= set([6,7,8])
    if x <= 0:
        direction_t -= set([1,4,6])
    if x >= (x_length-1):
        direction_t -= set([3,5,8])
    rnd=rd.sample(direction_t,1)
    t_y,t_x = y,x
    if rnd[0] in [1,4,6]:
        t_x-=1
    if rnd[0] in [3,5,8]:
        t_x+=1
    if rnd[0] in [1,2,3]:
        t_y-=1
    if rnd[0] in [6,7,8]:
        t_y+=1
    return [t_y,t_x]

def check_arr(y_l,arr_t):
    for i in range(y_l):
        if 0 in arr_t[i]:
            return True
    return False

def drunken_bug():
    xlength,ylength,xspot,yspot = map(int,input().split(','))
    arr=[[0]*xlength for i in range(ylength)]
    circle=0
    arr[yspot][xspot]=1
    while check_arr(ylength,arr):
        tempxy = move(yspot,xspot,ylength,xlength)
        yspot =tempxy[0]
        xspot =tempxy[1]
        arr[yspot][xspot]+=1
        circle+=1
    for i in range(ylength):
        print(arr[i])
    print('반복횟수 : {0}'.format(circle))
drunken_bug()

C#

• 문제 해결을 위한 Roach 클래스 생성
• 모든 셀을 방문했는지 확인: 남은 셀 카운트
• 반드시 한 칸은 이동하는 것으로 가정 (제자리에 있을 경우도 카운트 할 경우 45라인 조건 삭제)

using System;
using System.Linq;

namespace CD038
{
    class Program
    {
        static void Main(string[] args)
        {
            Roach roach = new Roach(20, 20, 5, 5);
            roach.LetMeMove();
            roach.DisplayResult();
        }
    }

    class Roach
    {
        private int scaleY, scaleX; // 매트릭스 크기
        private int[,] matrix; // 매트릭스 방문횟수
        private int remainCount; // 방문하지 않은 셀 갯수
        private int moveCount = 0; // 바퀴벌레 이동 횟수
        private int posY, posX; // 바퀴벌레 현재 위치

        // constructor
        public Roach(int scaleY, int scaleX, int posY, int posX)
        {
            this.scaleY = scaleY; this.scaleX = scaleX;
            remainCount = scaleY * scaleX;
            matrix = new int[scaleY, scaleX];
            this.posY = posY; this.posX = posX;
        }

        // 바퀴벌레 이동
        public void LetMeMove()
        {
            matrix[posY, posX] += 1; remainCount--; // 초기 위치
            Random rnd = new Random();
            while (remainCount > 0)
            {
                int nextY, nextX; // 다음 이동 예상 위치
                do
                {
                    int dy = rnd.Next(-1, 2), dx = rnd.Next(-1, 2);
                    nextY = posY + dy; nextX = posX + dx;
                } while ((nextY == posY && nextX == posX) || // 반드시 이동하는 것으로 가정
                        nextY < 0 || nextY >= scaleY || nextX < 0 || nextX >= scaleX);

                posY = nextY; posX = nextX;
                if (matrix[posY, posX] == 0) { remainCount--; }
                matrix[posY, posX] += 1;
                moveCount++;
            }
        }

        // 결과 출력
        public void DisplayResult()
        {
            // 움직인 횟수 최대값의 길이 -> 셀 출력 길이 설정
            int maxLength = (from int count in matrix select count).Max().ToString().Length;

            for (int row = 0; row < scaleY; row++)
            {
                for (int col = 0; col < scaleX; col++)
                {
                    Console.Write(matrix[row, col].ToString().PadLeft(maxLength + 1));
                }
                Console.WriteLine();
            }
            Console.WriteLine($"Move count: {moveCount}");
        }
    }
}

from random import randint

def cockroach(m,n,x,y):
    lis = [[0]*m for i in range(n)]
    lis[y][x] = 1

    while list(lis[y][x] for y in range(n) for x in range(m)).count(0) != 0:

        rs = randint(-1,1),randint(-1,1)

        if -1<x+rs[0]<m and -1<y+rs[1]<n:
            x,y = x+rs[0],y+rs[1]
            lis[y][x] += 1

    for x in lis:
        print(x)

    print(sum(list(lis[y][x] for y in range(n) for x in range(m))))

import java.util.Random;
import java.util.Scanner;

public class RandomWalk {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        Random random = new Random();

        System.out.println("배열의 행, 열 크기를 입력하세요 : ");
        int array [][] = null;
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        int count1, count2;

        System.out.println("시작 지점 입력 : ");
        int p, q;
        while(true) {
            p = scanner.nextInt();
            q = scanner.nextInt();
            if(p < x && p >= 0 && q < y && q >= 0) break;
            System.out.println("다시 입력하세요.");
        }

        array = new int [x][];
        for(int i=0; i < x; i++) {
            array[i] = new int[y];
        }

        array[p][q] = 1;
        while(true) {
            count1 = random.nextInt(3) - 1;
            count2 = random.nextInt(3) - 1;
            p += count1;
            q += count2;
            if(p < 0 || q < 0 || p >= x || q >= y) {
                p -= count1;
                q -= count2;
                continue;
            } else {
                array[p][q]++;
            }
            int sum = 0;
            out:
                for(int i = 0; i < x; i++) {
                    for(int j = 0; j < y; j++) {
                        if(array[i][j] == 0) {
                            break out;
                        } else sum++;
                    }

                }
                if(sum == x * y) break;
        }
        int total = 0;
        for(int i = 0; i< x; i++) {
            for(int j = 0; j < y; j++) {
                total += array[i][j];
                System.out.printf("%2d ", array[i][j]);
            }
            System.out.println();
        }
        System.out.println("총 움직인 횟수 : " + (total - 1));
    }
}

import random
import math
from copy import copy

direction = ((-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1))

def is_finished(L):
    for a in L:
        for b in a:
            if b == 0: return False
    return True

def showWalks(L):
    Q = [list(map(str, a)) for a in L]        
    return '\n'.join(list(map(lambda x : ' '.join(x), Q)))

def RandomWalk(m, n, x, y):
    L = [[0]*n for i in range(m)]
    L[x][y] = 1
    is_out = lambda x, y : True if x<0 or y<0 or x>=m or y>=n else False
    walks = 0
    while not is_finished(L): #전부 다 밟았는지
        while True: #밖에 안 나가도록
            dx, dy = direction[math.floor(8*random.random())]
            if is_out(x+dx, y+dy):
                continue
            else:
                x += dx
                y += dy
                L[x][y] += 1
                walks += 1
                break
    return [L, walks]

>>> T = RandomWalk(5,4, 0,0)

>>> print("각 칸에 바퀴벌레가 멈추었던 횟수 :\n" + showWalks(T[0]))

각 칸에 바퀴벌레가 멈추었던 횟수 :
2 1 1 1
5 4 1 2
1 3 7 3
1 3 6 1
2 3 3 1
>>> print("바퀴벌레가 움직인 횟수 :", T[1])

바퀴벌레가 움직인 횟수 : 50

from random import randint, choice

r, c, x, y = input().split()

r, c = int(r), int(c)
size, size_index = [], []
start = [int(x), int(y)]

for a in range(int(r)):
    size.append([])
    for b in range(int(c)):
        size[a].append(0)
        size_index.append([a, b])


def list_sum(l1, l2):
    result = []
    for d in range(len(l2)):
        result.append(l1[d] + l2[d])

    return result


def random_walk(row, column, start_l):
    next_p = [start_l[0] + randint(-1, 1), start_l[1] + randint(-1, 1)]
    if next_p[0] > row or next_p[1] > column or next_p[0] < 0 or next_p[1] < 0 or next_p == start_l:
        while 1:
            next_p = [start_l[0] + randint(-1, 1), start_l[1] + randint(-1, 1)]
            if 0 <= next_p[0] < row and 0 <= next_p[1] < column and next_p != start_l:
                break

    return next_p


size[start[0]][start[1]] += 1
size_index.remove([start[0], start[1]])

move_count = 0

while len(size_index) > 0:
    position = random_walk(int(r)-1, int(c)-1, start)
    size[position[0]][position[1]] += 1
    if position in size_index:
        size_index.remove(position)
    move_count += 1
    start = position

print(move_count)

파이썬 3입니다.

numpy의 randint를 이용하여 무작위적으로 좌표를 움직이는 함수를 정의하고 문제를 해결했습니다.

from numpy.random import randint

col, row, i_col, i_row = tuple(map(int, input().split()))  # 가로 크기, 세로 크기, 초기 위치 (가로, 세로)

# 격자 생성
grid = [[0 for _ in range(col)] for _ in range(row)]


def r_dir(r, c, i0, j0):  # (행, 열, 현재 행, 현재 열): 랜덤으로 좌표 변경
    if i0 == j0 == 0:
        d = randint(3)
        return i0 + (d in (1, 2)), j0 + (d in (0, 2))
    elif i0 == 0 and j0 == c - 1:
        d = randint(3)
        return i0 + (d in (1, 2)), j0 - (d in (0, 1))
    elif i0 == r - 1 and j0 == 0:
        d = randint(3)
        return i0 - (d in (1, 2)), j0 + (d in (0, 1))
    elif i0 == r - 1 and j0 == c - 1:
        d = randint(3)
        return i0 - (d in (0, 1)), j0 - (d in (1, 2))
    elif i0 == 0 and j0 not in (0, c - 1):
        d = randint(5)
        return i0 + (d in (2, 3, 4)), j0 + (d in (0, 4)) - (d in (1, 2))
    elif i0 == r - 1 and j0 not in (0, c - 1):
        d = randint(5)
        return i0 - (d in (1, 2, 3)), j0 + (d in (0, 1)) - (d in (3, 4))
    elif i0 not in (0, r - 1) and j0 == 0:
        d = randint(5)
        return i0 + (d in (0, 1)) - (d in (3, 4)), j0 + (d in (1, 2, 3))
    elif i0 not in (0, r - 1) and j0 == c - 1:
        d = randint(5)
        return i0 + (d in (0, 1)) - (d in (3, 4)), j0 - (d in (1, 2, 3))
    else:
        d = randint(8)
        return i0 + (d in (5, 6, 7)) - (d in (1, 2, 3)), j0 + (d in (0, 1, 7)) - (d in (3, 4, 5))


def end_cond(gr):  # 메인 코드의 종료 조건
    for r1 in range(len(gr)):
        if 0 in gr[r1]:
            return False
    return True


i1, j1 = i_row, i_col  # 좌표에 초기값 입력
N = 0  # 바퀴벌레가 이동한 횟수

while True:
    if end_cond(grid):
        break
    grid[i1][j1] += 1
    i1, j1 = r_dir(row, col, i1, j1)
    N += 1

# 출력

print('각 칸에 바퀴벌레가 멈추었던 횟수:')

for i in range(row):
    for j in range(col):
        print('{:3d}'.format(grid[i][j]), end=' ')
    print()

print('\n 바퀴 벌레는 총 {}만큼 움직였다'.format(N))

import random
a=10
b=10
d={}
c=0
n=0

for i in range(a):
    for k in range(b):
        d[(i,k)]=0

m=''
for i in range(b):
    m+='\n\n'
    for k in range(a):
        m+=str(d[(k,b-1-i)])+'   '
print(m)
print('<<격자 모양>>')

ox=random.choice(list(range(a)))
oy=random.choice(list(range(b)))
l=[ox,oy]
t=(l[0],l[1])
d[t]+=1

m=''
for i in range(b):
    m+='\n\n'
    for k in range(a):
        m+=str(d[(k,b-1-i)])+'   '
print(m)
print(str(t)+'에서부터 시작.')
while c==0:    
    while True:
        x=random.choice([-1,0,1])
        y=random.choice([-1,0,1])
        if x!=0 or y!=0:
            l[0]+=x
            l[1]+=y
            if 0<=l[0]<a and 0<=l[1]<b:
                if x>0 and y>0:
                    print('이동 방향은 '+'↗'+'방향')
                elif x>0 and y==0:
                    print('이동 방향은 '+'→'+'방향')
                elif x>0 and y<0:
                    print('이동 방향은 '+'↘'+'방향')
                elif x==0 and y>0:
                    print('이동 방향은 '+'↑'+'방향')
                elif x==0 and y<0:
                    print('이동 방향은 '+'↓'+'방향')
                elif x<0 and y<0:
                    print('이동 방향은 '+'↙'+'방향')
                elif x<0 and y>0:
                    print('이동 방향은 '+'↖'+'방향')
                else:
                    print('이동 방향은 '+'←'+'방향')
                break
            else:
                l[0]-=x
                l[1]-=y                
                continue
        else:
            continue
    t=(l[0],l[1])
    print('이동할 좌표'+str(t))
    d[t]+=1
    g=d[t]
    d[t]='['+str(d[t])+']'
    n+=1
    m=''
    for i in range(b):
        m+='\n\n'
        for k in range(a):
            m+=str(d[(k,b-1-i)])+'   '
    print(m)
    d[t]=g    
    v=1
    for i in range(a):
        for k in range(b):
            v*=d[(i,k)]
    c=v
print('\n\n결과:')
print('초기값:' +str([ox,oy]))
print('이동한 총 횟수 '+str(n))

파이썬 입니다. 격자를 문자열로 표현하려 해 보았습니다. 격자에서 멈춘 횟수의 자릿수가 바뀌거나 현재 위치를 표기하면 같은 줄의 문자들의 위치가 조금씩 밀려나는 현상이 나타났는데, 상황에 무관하게 문자 위치가 유지되는 코드를 짤 수 있도록 앞으로 더 노력해야 할 것 같습니다. 재미있고 유익한 문제 올려주셔서 감사합니다. ^^

#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
/*
'술취한 바퀴벌레' 문제라고도 한다. 다음과 같은 격자에 술취한 바퀴벌레가 있다고 해 보자

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

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

입력
격자의 가로, 세로 크기

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

bool CheckIdx(int n, int m, int cn, int cm) {
    if (cn < n && cn >= 0) {
        if (cm < m && cm >= 0) { return true; }
        else { return false; }
    }
    else { return false; }
}

void Func(int n, int m) {
    int **arr;
    arr = new int*[n];
    for (int i = 0; i < n; i++)
        arr[i] = new int[m];

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

    int sn, sm; //바퀴 벌레 시작 위치
    sn = rand() % n;
    sm = rand() % m;

    vector<pair<int, int>> v;
    v.reserve(8);
    int num;
    int count = -1;
    bool check;
    while (1) {
        arr[sn][sm] += 1;
        count++;

        //바퀴벌레의 이동을 하나하나 다 살펴 볼수있음
        /*for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << arr[i][j] << "\t";
            }
            cout << endl;
        }
        cout << "현재 바퀴벌레 위치: arr[" << sn << "][" << sm << "]" << endl;
        cout << "현재까지 이동 횟수: " << count << "회" << endl;
        system("pause");
        cout << endl;
        */

        if (CheckIdx(n, m, sn - 1, sm - 1)) { v.push_back(make_pair(sn - 1, sm - 1)); }
        if (CheckIdx(n, m, sn - 1, sm)) { v.push_back(make_pair(sn - 1, sm)); }
        if (CheckIdx(n, m, sn - 1, sm + 1)) { v.push_back(make_pair(sn - 1, sm + 1)); }
        if (CheckIdx(n, m, sn, sm - 1)) { v.push_back(make_pair(sn, sm - 1)); }
        if (CheckIdx(n, m, sn, sm + 1)) { v.push_back(make_pair(sn, sm + 1)); }
        if (CheckIdx(n, m, sn + 1, sm - 1)) { v.push_back(make_pair(sn + 1, sm - 1)); }
        if (CheckIdx(n, m, sn + 1, sm)) { v.push_back(make_pair(sn + 1, sm)); }
        if (CheckIdx(n, m, sn + 1, sm + 1)) { v.push_back(make_pair(sn + 1, sm + 1)); }

        num = rand() % v.size();
        sn = v[num].first;
        sm = v[num].second;
        v.clear();

        check = true;
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < m; j++) 
                if (arr[i][j] == 0) { check = false; }

        if (check) { break; }
    }
    cout << "===================끝====================" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << arr[i][j] << "\t";
        }
        cout << endl;
    }
    cout << "바퀴 벌레 총 이동횟수: " << count << "회" << endl;

    for (int i = 0; i < n; i++)
        delete[] arr[i];
    delete[] arr;
}

int main() {
    srand((unsigned int)time(NULL));
    Func(10, 10);
}

from random import *
import os

def show_map(m):                #맵을 출력해주는 함수
    for j in range (0,y):   
        for i in range (0,x):
            if m[j][i]>0:
                if i==xx and j==yy:   # 방금 이동한 위치는 빨간색으로 표시
                    print ("\x1b[31m"+"%5d" %m[j][i]+"\x1b[0m",end=' ')
                else:                 # 한번 이상 이동한 곳은 빨간색으로 표시
                    print ("\x1b[34m"+"%5d" %m[j][i]+"\x1b[0m",end=' ')
            else:                      #한번도 가지 않은곳은 흰색으로 표시
                print ("\x1b[37m"+"%5d" %m[j][i]+"\x1b[0m",end=' ')                    
        print ()

def find_0(m):              #맵에 0이 포함되어 있으면 True 반환
    for j in range (0,y):   
        if 0 in m[j]:
            return True            

temp=str(input('x(가로길이) y(세로길이) z(처음위치)...')).split(' ')
x,y,z=int(temp[0]),int(temp[1]),int(temp[2])
yy,xx=z//y,z%x      #xx,yy는 현재위치를 위미하며, 처음위치를 나타냄

m=[]
for j in range (0,y):           #맵m을 모두 0으로 초기화 함
    temp=[]
    for i in range (0,x):
        temp.append(0)
    m.append(temp)

m[yy][xx]+=1
show_map(m)

while(1):
    if find_0(m) !=True:    #맵에 0에 포함되어 있지 않으면 프로그램 루프 종료
        break

    direction=randint(0,7)
    if direction==0:     #위로 이동
        if yy!=0:
            yy-=1
        else:
            m[yy][xx]-=1

    elif direction==1:     #아래로 이동
        if yy!=(y-1):
            yy+=1
        else:
            m[yy][xx]-=1

    elif direction==2:     #오른쪽으로 이동
        if xx!=(x-1):
            xx+=1
        else:
            m[yy][xx]-=1

    elif direction==3:     #왼쪽으로 이동
        if xx!=0:
            xx-=1
        else:
            m[yy][xx]-=1

    elif direction==4:     #오른쪽 위
        if xx!=(x-1) and yy!=0:
            xx+=1
            yy-=1
        else:
            m[yy][xx]-=1

    elif direction==5:     #오른쪽 아래
        if xx!=(x-1) and yy!=(y-1):
            xx+=1
            yy+=1
        else:
            m[yy][xx]-=1

    elif direction==6:     #왼쪽 위
        if xx!=0 and yy!=0:
            xx-=1
            yy-=1
        else:
            m[yy][xx]-=1

    elif direction==7:     #왼쪽 아래
        if xx!=0 and yy!=(y-1):
            xx-=1
            yy+=1   
        else:
            m[yy][xx]-=1     

    os.system('CLS')
    m[yy][xx]+=1
    print('바퀴벌레의 현재위치 xx=',xx,'yy=',yy,'\n')
    show_map(m)

sum=0
for j in range (0,y):   
    for i in range (0,x):
        sum+=m[j][i]
print ('\n바퀴벌레의 총 이동거리 : ',sum)

import random
def random_work(rlim, clim, row, col):
    grid = [[0]*clim for _ in range(rlim)]
    grid[row][col] = 1
    cnt = 0
    while not all([all(grid[i]) for i in range(rlim)]):
        while 1:
            direction = [random.randint(-1, 1) for _ in range(2)]
            if not all(direction) and (0 <= row+direction[0] < len(grid)) and (0 <= col+direction[1] < len(grid[0])):
                row += direction[0]
                col += direction[1]
                break

        cnt += 1
        grid[row][col] += 1
    print('각 칸에 바퀴벌레가 멈추었던 횟수:\n {}\n바퀴벌레가 움직인 횟수: {}'.format(grid, cnt))

if __name__ == '__main__':
    rlim, clim = 100, 100
    row, col = 2, 2
    random_work(rlim, clim, row, col)

import random

def sol(x_size, y_size) :
    d_list, m, position = [-1, 0, 1], [0 for i in range(x_size*y_size)], (random.randint(0, x_size-1), random.randint(0, y_size-1))
    counter = 0
    m[(position[1]*x_size)+position[0]] += 1
    print("Initial point : ", position)
    while True :
        d_position = (d_list[random.randint(0, 2)], d_list[random.randint(0, 2)]) # 이동 방향 결정
        if d_position == (0, 0) : continue
        if 0 <= (position[0]+d_position[0]) < x_size and 0<=(position[1]+d_position[1]) < y_size :
            position = (position[0]+d_position[0], position[1]+d_position[1]) # 위치 갱신
            m[(position[1]*x_size)+position[0]] += 1 # 갱신된 위치 카운트
            counter += 1
        else : continue

        if not 0 in m : #모든 좌표를 방문한 경우 결과 출력
            justSize = len(str(max(m)))+1
            for r in range(0, y_size) :
                r_txt = ""
                for c in range(0, x_size) :
                    r_txt += str(m[r*x_size+c]).rjust(justSize)
                print(r_txt)

            return "count : "+str(counter)
    return counter

if __name__ == "__main__" :
    print(sol(20, 20))

결과

Initial point :  (1, 8)
 14 28 29 29 16 13 20 15 12 11 11 18 21 19 19 19 17 12 16 13
 24 41 37 35 25 28 31 24 22 24 21 21 31 42 34 29 23 19 22 17
 29 33 27 23 23 23 21 15 27 28 25 20 22 32 33 27 22 24 26 15
 22 40 26 20 23 20 11 26 13 18 17 25 21 25 25 20 21 18 26  9
 21 28 26 30 31 19 18 20 21 19 25 17 23 24 16 18 19 28 16 10
 14 26 26 30 34 19 27 22 23 21 23 24 27 23 23 22 31 25 13  6
 17 30 30 29 28 34 27 30 25 23 24 24 36 28 21 19 23 21 14  7
 14 34 33 17 30 32 29 24 19 18 21 22 21 16 12 15 13 15 20 15
 24 29 30 21 24 28 18 20 24 17 14 19 18 14  9 12 13 12 16 11
 24 28 18 32 24 24 19 18 18 11 15 15 23 16  6  7  8 18 13  4
 16 26 25 23 30 35 22 19 10 19  9  9 14 10  7  6  8 17 13  3
 12 27 23 23 25 32 26 14 12  9  7  6  5  9 12  8 12 10  9  4
 18 15 24 17 24 24 27 15  9 11  8  6 14 11 12 11 13 14  1  1
 13 17 23 18 23 29 27 12 17  7  6 11 12 12 17 15 15 11  8  1
  7 24 21 14 17 27 20 25 12 10 17 18 14 16 18 13 16 18  9  3
 10 28 17 16 27 12 34 23 22 20 18 17 17 15 21 20 18 18 17 12
 16 24 25 16 18 24 26 33 20 18 19 20 11 12 19 21  9 18 19 14
  7 25 23 22 24 32 30 24 24 16 22 20 13 12 17 16 13 21 27 13
 11 25 32 20 16 25 31 29 32 16 15 22 29 11 11 14 13 20 20 15
 12 19 11 10 11 13 21 21 12 13 10 14 17 10  2  4 10 10  9  8
count : 7637

100 x 100 정도의 사이즈라면 '인내할만한' 시간 안에 결과가 나오지만 1000 단위 이상은 확실히 오래걸립니다.

public class DrunkBaTeacher {
    private static int[][] MAP;
    public static void main(String[] args) {
        int x = 0, y = 0, moveCNT = 0, checkCNT = 0;
        int baX = 0, baY = 0;
        int way_FLAG = 0;
        boolean sr_FLAG = true;
        boolean flag = true;
        // Straight / Reverse
        System.out.print("가로의 길이 : ");
        x = KunheeUtil.scanIntData(x);
        System.out.print("세로의 길이 : ");
        y = KunheeUtil.scanIntData(y);
        MAP = new int[x][y];

        baX = new Random().nextInt(x);
        baY = new Random().nextInt(y);

        MAP[baX][baY] = 1;

        while(flag) {
            way_FLAG = new Random().nextInt(3);
            sr_FLAG = new Random().nextBoolean();
            checkCNT = 0;
            /* way_FLAG
             *  0: 직선, 1: 세로, 2: 대각선
             * sr_FLAG
             *  TRUE: 직진(+), FALSE: 후진(-)
             */
            if(way_FLAG == 0) {
                baY = sr_FLAG ? baY+1 : baY-1;
            }else if(way_FLAG == 1) {
                baX = sr_FLAG ? baX+1 : baX-1;
            }else {
                if(sr_FLAG) {
                    baX++;
                    baY++;
                }else {
                    baX--;
                    baY--;
                }
            }

            baX = (baX == x) ? 0 : baX;
            baY = (baY == y) ? 0 : baY;
            baX = (baX == -1) ? x-1 : baX;
            baY = (baY == -1) ? y-1 : baY;

            MAP[baX][baY]++;
            moveCNT++;

            for (int i = 0; i < MAP.length; i++) {
                for (int j = 0; j < MAP[i].length; j++) {
                    if(MAP[i][j] == 0) checkCNT++;
                }
            }
            flag =  checkCNT > 0 ? true : false;
        }

        System.out.println("- 움직인 횟수: " + moveCNT);
        System.out.println("- 마지막 위치: " + (baX+1) + " 행  " + (baY+1) + " 열");
        System.out.println("\n< MAP >\n");
        for (int i = 0; i < MAP.length; i++) {
            for (int j = 0; j < MAP[i].length; j++) {
                if(i == baX && j == baY) {
                    System.out.print("['" + MAP[i][j] + "']");
                }else {
                    System.out.print("[ " + MAP[i][j] + " ]");
                }

            }
            System.out.println();
        }
    }
}

import random
import numpy as np

def Sheet():
    count=0
    A=int(input("격자의 가로길이 : "))
    B=int(input("격자의 세로길이 : "))
    a = np.zeros((A,B))
    c = int(input("행 입력 : "))-1  # 시작위치지정
    d = int(input("열 입력 : "))-1
    print(a)
    while True:
        total=0 
        if (c==0 and d==0):  # 좌측 위 아래 끝
            q = random.randrange(0,3)
            if q==0:
                c+=1
            elif q==1:
                c+=1
                d+=1
            elif q==2:
                d+=1
            a[c,d]+=1          # 랜덤의 수가 나온이후 랜덤자리에 1을 넣어줘서 지나갔다는 흔적을 남김
        elif  (c==A-1 and d==0):
            w= random.randrange(0,3)
            if w==0:
                c-=1
            elif w==1:
                c-=1
                d+=1
            elif w==2:
                d+=1
            a[c,d]+=1
        elif (c==0 and d==B-1):  # 우측 위 아래 끝
            z=random.randrange(0,3)
            if z==0:
                d-=1
            elif z==1:
                c+=1
                d-=1
            elif z==2:
                c+=1
            a[c,d]+=1
        elif (c==A-1 and d==B-1):
            r=random.randrange(0,3)
            if r==0:
                c-=1
            elif r==1:
                d-=1
            elif r==2:
                c-=1
                d-=1
            a[c,d]+=1
        elif c==0:     #0번째 줄 
            t = random.randrange(0,5)
            if t==0:
                d-=1
            elif t==1:
                d+=1
            elif t==2:
                c+=1
                d-=1
            elif t==3:
                c+=1
            elif t==4:
                d+=1
                c+=1
            a[c,d]+=1
        elif c==A-1:     # 6번째 줄
            t = random.randrange(0,5)
            if t==0:
                d-=1
            elif t==1:
                d+=1
            elif t==2:
                c-=1
                d-=1
            elif t==3:
                c-=1
            elif t==4:
                d+=1
                c-=1
            a[c,d]+=1
        elif d==0:
            y=random.randrange(0,5)
            if y==0:
                c-=1
            elif y==1:
                c-=1
                d+=1
            elif y==2:
                d+=1
            elif y==3:
                c+=1
            elif y==4:
                c+=1
                d+=1
            a[c,d]+=1
        elif d==B-1:
            y=random.randrange(0,5)
            if y==0:
                c-=1
            elif y==1:
                c-=1
                d-=1
            elif y==2:
                d-=1
            elif y==3:
                c+=1
            elif y==4:
                c+=1
                d-=1
            a[c,d]+=1
        else:
            y=random.randrange(0,8)
            if y==0:
                c-=1
                d-=1
            elif y==1:
                c-=1
            elif y==2:
                c-=1
                d+=1
            elif y==3:
                d-=1
            elif y==4:
                d+=1
            elif y==5:
                c+=1
                d-=1
            elif y==6:
                c+=1
            elif y==7:
                c+=1
                d+=1
            a[c,d]+=1
        count+=1
        for i in range(A):    # 반복문을 통해서 시트안의 자취흔적 조사 
            for j in range(B):
                if a[i,j]>0:
                    total+=1
                    if total==A*B:
                        break
            if total==A*B:
                break
        if total==A*B:
            break
    print(a)
    print(count)
Sheet()

고수분들 풀이보니까 제가 너무 허접한거같네요,,

시간이 많이 드네요..

import random

#가로,세로,초기위치
n,m,s = 10,10,[5,5]

#필드생성
room = [[0]*n for _ in range(m)]

#이동방향
move_list = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,-1)]

#좌표이동 후 횟수측정
count = 0
countdown = n*m
while countdown>0:
    move = move_list[random.randint(0,len(move_list)-1)]
    if 0<=s[0]+move[0]<n and 0<=s[1]+move[1]<m:
        if room[s[0]+move[0]][s[1]+move[1]] == 0: countdown -=1
        room[s[0]+move[0]][s[1]+move[1]]+=1
        count+=1
        s[0]+=move[0]
        s[1]+=move[1]
    else : continue

print('=='*11,' 칸마다 방문수 ','=='*11)
for i in room:
    for j in i:
        print(f'{j:5d}',end=' ')
    print()
print(f'\n바퀴벌래의 이동수 : {count}칸')

from random import *

#arr 원소에 0을 포함하는지 여부 판단 함수
def fun (arr):
    f=[]
    for i in arr:
        if 0 not in i:
            f.append(0)
    if len(f) == len(arr):
        return False
    else:
        return True

inp = list(map(int,input('격자의 가로,세로 크기 입력').split(',')))
start = list(map(int,input('초기위치 row,column :').split(',')))
arr=[[0 for _ in range(inp[1])] for _ in range(inp[0])]

r=start[0]
c=start[1]
n=0
arr[r][c]=1 #초기값을 1로 둘지 말지는 선택 가능

print(arr)
#배열의 0이 없어질때 까지 바퀴벌레 랜덤 이동 함수
while fun(arr):
    row=r+randint(-1,1)
    col=c+randint(-1,1)
    if (row>=0 and row<inp[0]) and (col>=0 and col<inp[1]):
        if not (r==row and c==col):
            r=row
            c=col
    arr[r][c] +=1
    n+=1

print('이동횟수는',n,'회 입니다')
for k in arr:
    for i in k:
        print(i,end=' ')
    print('')

주석이 부실하긴한데, random함수를 이용해서 바퀴벌레의 랜덤한 이동칸수를 정했어요 row와 column성분을 각각 무작위로 뽑았고, 만일 row 와 col 성분 모두 0칸을 움직이는경우는 움직임이 없다고 판단하여, 이동횟수를 카운트 하지 않도록 했습니다.

import random
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
from matplotlib.animation import FuncAnimation, PillowWriter 

N = 700
X,Y = [],[]

col, row = 30,30
cnt = [[0 for value in range(col)] for value in range(row)]
np_cnt = np.array(cnt)
cnt_fla = cnt_flatten = np_cnt.flatten()

x = random.randint(0,col-1)
y = random.randint(0,row-1)

while sum(cnt_fla) <N:
    x_max = min(x+1, col-1)
    x_min = max(x-1, 0)

    y_max = min(y+1, row-1)
    y_min = max(y-1, 0)

    x=random.randint(x_min, x_max)
    y=random.randint(y_min, y_max)

    cnt[y][x] += 1
    np_cnt = np.array(cnt)
    cnt_fla = cnt_flatten = np_cnt.flatten()
    X.append(x)
    Y.append(y)

plt.plot(X,Y)
plt.show()

import random
import numpy as np

class Action:
  def __init__(self, grid_x, grid_y, initial_x, initial_y):
    self.grid = np.zeros((grid_x, grid_y))
    self.x, self.y = initial_x, initial_y
    #return self.x, self.y        

  def action(self,x, y):
    self.x = x
    self.y = y
    self.x_temp = self.x
    self.y_temp = self.y
    action = random.randint(1,8)

    if action == 1:
      self.x_temp-=1
    if action == 2:
      self.x_temp-=1; self.y_temp-=1
    if action == 3:
      self.y_temp+=1
    if action == 4:
      self.x_temp+=1; self.y_temp+=1
    if action == 5:
      self.x_temp += 1
    if action == 6:
      self.x_temp+=1; self.y_temp-=1
    if action == 7:
      self.y_temp-=1
    if action == 8:
      self.x_temp-=1; self.y_temp-=1

    if self.x_temp==-1 or self.x_temp == self.grid.shape[0]:
      self.x = self.x
    else:
      self.x = self.x_temp

    if self.y_temp==-1 or self.y_temp == self.grid.shape[1]:
      self.y = self.y
    else:
      self.y = self.y_temp

    #self.grid[self.x,self.y] += 1 
    return self.x, self.y 

  def grid_update(self, x, y):
    self.x = x; self.y = y
    if self.x>=0 and self.x<self.grid.shape[0] and self.y>=0 and self.y<self.grid.shape[1]:
      #print(x,y)
      self.grid[x,y]+=1

grid_x, grid_y, initial_x, initial_y =input().split(" ")
grid_x, grid_y, initial_x, initial_y = int(grid_x), int(grid_y), int(initial_x), int(initial_y)

drunken = Action(grid_x, grid_y, initial_x, initial_y)
x, y = initial_x, initial_y

count = 0
while True:
  x_new, y_new = drunken.action(x,y)
  drunken.grid_update(x_new, y_new)
  if x_new != x or y_new != y:
    count+=1
  if np.count_nonzero(drunken.grid)==grid_x*grid_y:
    print("각 칸에 바퀴벌레가 멈추었던 횟수:\n", count)
    print("바퀴벌레가 움직인 횟수:\n",drunken.grid)
    break
  x, y = x_new, y_new

import random

def mapPrint(C, R, mapW):
    for r in range(R):
        for c in range(C):
            print('%3d' %(mapW[(r,c)]), end='')
        print()


def randomWalk(C, R, iniPos):
    dr = [-1,-1,0,1,1,1,0,-1]
    dc = [0,1,1,1,0,-1,-1,-1]
    mapW = {}
    pos = (iniPos[0],iniPos[1])
    mapW[pos] = 1
    move = 0
    while len(mapW) < C*R:
        move += 1        
        while True:
            i = random.randint(0,7)
            r, c = pos[0]+dc[i], pos[1]+dr[i]
            if 0<=c<C and 0<=r<R:
                pos=(r,c)
                break
        if pos not in mapW:
            mapW[pos]=0
        mapW[pos] += 1
    print('각 칸에 바퀴벌레가 멈추었던 횟수')
    mapPrint(C, R, mapW)
    print('바퀴벌레가 움직인 횟수: ', move)

c=int(input("가로: "))
r=int(input("세로: "))
iniPos = list(map(int, input("바퀴벌레의 초기 위치: ").split()))
print(' ='*10)
randomWalk(c,r,iniPos)