Random Walk

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

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

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

입력

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

출력

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

심화문제

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


참고

출처: 위키백과

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

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

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

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

1개의 풀이가 있습니다.

Ruby

  • array manipulation의 효율적 처리
  • tiles 검색/수정은 hash로, 처리완료 체크는 Set로.
  • visit 발생한 요소를 삭제해서 비교 횟수 줄이기. Set이 empty가 될 때 까지 반복
require 'set'

X, Y = 100, 100; matrix = [*1..Y].product([*1..X]).to_set
Tile = Struct.new :x, :y, :stay, :visit
tiles = matrix.map {|e| [e, Tile.new(e[0],e[1],0,0)] }.to_h
at = ->x,y { tiles[[x,y]] || false }

crawl = ->bug { n=at[bug[0]+rand(-1..1),bug[1]+rand(-1..1)]; n ? [n.x,n.y] : bug }
trail = ->prev,now { prev==now ? at[*prev].stay+=1 : at[*now].visit+=1 }
move = ->bug { crawl[bug].tap {|e| trail[bug,e]} }

bug=[rand(X)+1,rand(Y)+1]; (bug=move[bug]; matrix.delete(bug)) until matrix.empty?
puts "total movements : #{tiles.values.map(&:visit).reduce :+}"
tiles.each_slice(X).each {|cols| cols.each { |e|
              print "[%3d (%3d)] " % [e[1].stay, e[1].visit]}; print "\n" }

성능

# 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

#=> examle) 10x10. stays(visits)
total movements : 753
[ 0 ( 1)] [ 8 ( 5)] [ 0 ( 2)] [ 1 ( 2)] [ 2 ( 4)] [ 3 ( 4)] [ 0 ( 1)] [ 4 ( 8)] [10 ( 7)] [16 ( 8)]
[ 3 ( 6)] [ 0 ( 9)] [ 0 ( 3)] [ 1 ( 6)] [ 2 ( 8)] [ 0 ( 6)] [ 1 ( 7)] [ 0 (10)] [ 0 (18)] [ 4 (10)]
[ 7 ( 7)] [ 0 ( 9)] [ 1 ( 9)] [ 1 ( 3)] [ 1 ( 8)] [ 0 ( 6)] [ 2 ( 9)] [ 1 ( 8)] [ 2 ( 5)] [ 3 ( 4)]
[ 3 ( 4)] [ 2 (10)] [ 1 ( 6)] [ 0 ( 7)] [ 1 ( 6)] [ 0 ( 9)] [ 0 ( 6)] [ 1 (10)] [ 1 ( 5)] [ 5 ( 7)]
[ 2 ( 6)] [ 0 ( 8)] [ 0 ( 7)] [ 0 (10)] [ 0 ( 6)] [ 2 ( 7)] [ 2 ( 7)] [ 1 ( 6)] [ 2 ( 8)] [ 3 ( 9)]
[ 6 ( 9)] [ 0 (13)] [ 3 (15)] [ 1 ( 8)] [ 1 (11)] [ 1 ( 7)] [ 2 ( 5)] [ 0 ( 8)] [ 2 (10)] [ 8 ( 5)]
[ 1 ( 5)] [ 0 (17)] [ 0 ( 8)] [ 2 (14)] [ 2 ( 4)] [ 0 ( 5)] [ 0 ( 3)] [ 1 ( 8)] [ 3 (11)] [ 7 ( 7)]
[13 ( 7)] [ 3 (11)] [ 0 (14)] [ 2 (11)] [ 2 ( 5)] [ 0 ( 3)] [ 0 ( 3)] [ 0 ( 4)] [ 3 (11)] [ 7 ( 8)]
[ 1 (10)] [ 3 (20)] [ 3 (25)] [ 2 (11)] [ 0 ( 4)] [ 1 ( 5)] [ 4 ( 6)] [ 0 ( 3)] [ 0 ( 5)] [14 (10)]
[22 ( 9)] [15 (17)] [13 (13)] [ 4 ( 7)] [ 6 ( 4)] [ 3 ( 4)] [ 2 ( 6)] [ 5 ( 3)] [ 8 ( 3)] [ 1 ( 1)]
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

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

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


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