C++ 바퀴벌레 랜덤워크

소개

배경) 다음과 같은 문제를 생각하자. 바퀴벌레가 방 안에 있다. 이 방은 사각형이고 바닥은 n*m개의 타일로 이루어져 있다. 바퀴벌레는 랜덤하게 타일에서 타일로 돌아다닌다. 바퀴벌레가 위치한 타일에서 주위의 8개 타일로(벽에 붙어 있을 때를 제외하고) 이동할 수 있는 확률이 모두 같다면 그 벌레가 마루의 모든 타일을 최소한 한 번 이상 방문하는 데 얼마나 오래 걸릴까?

이 문제를 확률 이론으로 풀기는 어려울 것이다. 하지만 컴퓨터를 이용하면 다음과 같이 쉽게 해결할 수 있다. n*m배열의 값은 각각의 타일을 바퀴벌레가 몇 번 방문했었는지를 나타낸다. 마루에서 바퀴벌레가 있는 타일의 위치를 (ibug, jbug)로 나타내면 이동 가능한 주위 8개 타일의 위치는 (ibug + imove[k], jbug + jmove[k])로 나타낼 수 있다. (단, 0 ≤ k ≤ 7) 주어진 8개의 타일 중 하나로 랜덤하게 이동하는 것은 0과 7사이의 랜덤 값에 의해서 결정된다. 물론 바퀴벌레는 방 밖으로 나갈 수가 없다. 따라서 벽에서 밖으로의 이동은 무시하고 그 위치에서 새로운 랜덤 값을 만들어서 이동한다. 바퀴벌레가 각각의 타일로 이동할 때 도착한 타일의 배열 값을 1씩 증가시키면 0이 아닌 값을 가진 타일은 바퀴벌레가 다녀갔던 곳임을 알 수 있다. 모든 타일을 바퀴벌레가 최소한 한 번 방문했다면 실험은 끝난다.



프로그램 명세) 위의 바퀴벌레 문제를 해결하는 프로그램을 아래의 제한 조건에 맞게 작성하시오.

(1) 10 ≤ n ≤ 90, 10 ≤ m ≤ 90의 범위 안의 값을 다룰 수 있다.

(2) 무한 루프를 피하기 위해서 반복의 최대값을 제한하라.

(3) 각 실험 마다 다음을 계산하라.

(a) 바퀴벌레의 총 이동 횟수

(b) 각 타일에 대한 바퀴벌레의 방문 횟수



분석 내용)

1) n=25, m=50인 경우에 대한 프로그램 명세 3의 a,b

2) n=11, 21, 31, 41, 51, 61, 71, 81, m=51인 경우 각각에 대하여 바퀴벌레의 출발점을 왼쪽 모서리 및 중앙으로 하고 바퀴벌레의 총 이동 횟수의 변화의 추이를 차트로 표현하라. 단 각 실험은 50번 이상 반복하여 그 평균값을 취하라.

3) 2의 각 경우에 대한 프로그램의 실행시간을 천분의 일초 단위로 계산하여 그 추이를 차트로 표현하라.

(clock() 함수를 이용)

컴파일 실행환경

Microsoft visual c++

참고자료

· 없음