[자료구조] 술취한 바퀴 시뮬레이션

소개글

유명한 술취한 바퀴시뮬레이션 문제죠.
한글 문서로 작성되어 있습니다.

목차

1. 문제
2. 문제분석
3. 알고리즘
4. 프로그램 소스
5. 실행결과
6. 결과토의

본문내용

1. 문제
한 (술취한) 바퀴벌레가 n*m 프기의 직사각형 방 중간의 한 타일 위에 있다. 바퀴벌레는 임의로 타일에서 타일으로 걸어간다. 바퀴벌레(벽 옆에 있지 않는 경우)가 현재 타일에서 그 주위 8개의 타일로 같은 확률을 가지고 움직인다고 가정하자. 이때 적어도 한 번씩 방의 모든 타일을 지나가는데 걸리는 시간은 얼마인가?
이것을 시뮬레이션하는 프로그램을 작성하라.

2. 문제 분석
이 프로그램은 다음과 같은 조건을 따라야 한다.
(a) m과 n의 값은 2< n 40, 2< m < 20으로 조정한다.
(b) 다음과 같은 경우에 대하여 실험한다.
1. n=15, m=15, 시작점:(9,9)
2. n=39, m=19, 시작점:(0,0)
(c) 반복 횟수가 유한해야 한다. 즉 실험중 바퀴벌레가 들어갈 수 있는 타일의 수의 최대값을 정한다.
(d) 각 실험에 대해 다음 결과를 출력한다.
1. 적법한 바퀴벌레의 총이동수
2. 마지막 count 배열

참고 자료

없음