<사고력 훈련 문제 #9>: random walk 문제

# random walk 술취한 바퀴벌레 문제 // 문제가 길다. 집중해서 살펴보자.

---

수학 분야에서 "random walk"로 불리워지며 오랫동안 관심의 대상이 되었던 많은 문제들이 있다. 이러한 문제 중 지극히 간단한 것조차도 해결하기 매우 어렵기 때문에 대부분의 문제들이 해결되지 못한 채 남아 있다. 그 하나의 예가 '술취한 바퀴벌레 문제'다.

 한 (술취한) 바퀴벌레가 $m$$\times$$n$ 크기의 직사각형 방 중간의 한 타일 위에 있다. 바퀴벌레는 임의로 타일에서 타일로 이동한다. 바퀴벌레가 현재 타일에서 그 주위 8개의 타일(벽 옆에 있지 않은 경우에 한해)로 같은 확률을 가지고 움직인다고 가정하자. 이 때 적어도 한 번씩 방의 모든 타일을 지나가는 데 걸리는 시간은 얼마인가?

 순수한 확률 이론 기법에 의해 이런 문제를 해결하는 것은 어렵지만, 컴퓨터를 이용하면 매우 쉽게 해결된다. 이러한 기법을 시뮬레이션(simulation)이라고 한다. 이 기법은 교통흐름, 재고관리 등을 예고하는데 광범위하게 사용되고 있다. 위의 문제는 다음과 같은 방법을 이용하여 표현할 수 있다.

 $m$$\times$$n$ 배열 tile은 방에서 바퀴벌레가 각 타일을 방문하는 횟수를 나타내는데 사용된다. 이 배열의 모든 원소의 초기값은 0이다. 방에서 바퀴벌레의 위치는 좌표(x, y)로 나타낸다. 이동시에는 이동의 유효성을 검사해야하므로, 유효성을 검사할 때는 좌표(xbug, ybug)로 검사한다.

 바퀴벌레의 8가지 가능한 이동은 타일들의 위치, 즉 (x + xmove[k], y + ymove[k])로 나타내며, 여기서 $k$는 $0$$\leq$$k$$\leq$$7$ 이고 xmove와 ymove를 이동할 때의 기준은 다음과 같다.

xmove[0] = -1        ymove[0] =  1

xmove[1] =  0        ymove[1] =  1

xmove[2] =  1        ymove[2] =  1

xmove[3] =  1        ymove[3] =  0

xmove[4] =  1        ymove[4] = -1

xmove[5] =  0        ymove[5] = -1

xmove[6] = -1        ymove[6] = -1

xmove[7] = -1        ymove[7] =  0

/* x에서의 마이너스는 좌측으로 이동함을 뜻하고 y에서의 마이너스는 위쪽으로 이동함을 뜻한다. */

/* 플러스는 위의 설명과 반대로 진행되는 것은 쉽게 이해할 수 있을 것이다. */

 이동을 나타낼 때는 배열을 선언해서 값을 미리 설정해놓을 수도 있고, 별도의 이동함수를 만들어 각 상황별 별도의 값을 리턴하게끔 만들 수 있다.

 주어진 정방의 8개의 타일 중 어느 하나로의 움직임은, 0과 7사이의 랜덤한 값 $k$를 생성함으로써 시뮬레이션 할 수 있다. 물론 바퀴벌레는 방 밖으로 벗어나 움직일 수 없으며, 벽 위로 움직이는 좌표는 무시되어야 하고 새로운 임의 조합에 의해 움직임이 형성된다.

 한 타일에 들어갈 때마다 해당하는 배열값이 증가되며 이것은 지금까지 바퀴벌레가 그 타일을 방문한 횟수를 나타내는 것이다. 모든 타일에 적어도 한 번은 들어왔을 때 그 실험은 종료된다. 이와 같은 시뮬레이션 실험을 수행하는 프로그램을 작성하라.

$(a)$    $m$과 $n$의 값은 $2<n$  $\leq$ $40$,    $2$  $\leq$  $m < 20$으로 조절하고,

$(b)$    다음과 같은 경우에 대하여 수행하라. (test data set)

$(1)$  $n = 15, m = 15, 시작점: (10, 10)$

$(2)$  $n = 39, m = 19, 시작점: (1, 1)$

$(c)$    반복 실행의 한계를 결정하라. 즉, 실험 중 바퀴벌레가 이동할 수 있는 횟수에 제한을 둔다. 이 가정은 프로그램이 

종료될 수 있도록 하기 위함이다. 최대 $50,000$으로 결정하는 것이 적당하다.

$(d)$    각 실험에 대해 다음 결과를 출력하라.

$(1)$ 적법한 바퀴벌레의 총 이동수

$(2)$ 실행 후 tile 배열. 이것은 움직임에 대한 밀도, 즉 방에서 움직임을 통해 닿게 되는 각 타일의 횟수이다.

# 풀이

---

 문제가 꽤나 길고 복잡해 보이지만, 실상은 매우 단순하다. 2차원 배열 혹은 1차원 배열로 타일을 생성한 후 바퀴벌레의 이동에 따라 해당 배열의 값을 증가시켜주면 된다. // 2차원 배열도 결국 메모리 상에 저장될 때는 선형(linear)형태로 저장 되기때문에, 1차원 배열로 봐도 무방하다. 아래의 코드는 1차원 배열로 구현한 예다.

 입력을 받는 부분과 예외를 처리하는 부분만 조금만 주의해서 본다면 어렵지 않음을 금방 알 수 있을 것이다. calloc 이라는 다소 어색한 함수도 등장하는데, 이는 메모리 할당과 배열을 0으로 초기화하는 작업을 동시해 해주는 calloc의 간편함 때문이다.

 아래의 코드에서는 바퀴벌레의 이동을 별도의 함수로 만들어 사용했지만, 전역 배열로 움직임을 사전 정의해둔 후 사용해도 상관 없다. 문제의 해결방법은 다양하다. 아래의 코드를 분석해보고 이해해보자.

/*************************************************
 ** random walk문제 <술취한 바퀴벌레>
*************************************************/

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

#define FALSE 0
#define TRUE 1

// 함수 원형 선언
int emptyTile(int, int);
int xmove(int);
int ymove(int);

// 입력 받는 배열의 크기 만큼 메모리를 할당할 예정
int *tile;	// 메모리 할당에 필요한 포인터 변수

/* 메인함수 */
void main()
{
	int m, n;	// 행과 열
	int x, y;	// 바퀴벌레의 처음 시작 위치를 나타낼 변수
	int i, j;	// 배열의 임시 index
	int k = 0;	// 움직일 수 있는 거리
	int xbug, ybug;	// 벌레의 위치좌표
	int totalmove = 0;	// 타일 방문 횟수의 최대값(50000)을 체크하기 위한 변수
	int total = 0;	// 각 타일에 방문한 횟수의 총합을 구하기 위한 변수

	int	movePossible = FALSE;	// 바퀴벌레가 움직일 수 있는지를 구하는 변수
	// 이 변수가 TRUE가 된다면, 모든 타일이 한 번씩 방문되었다는 것을 뜻하며
	// 바퀴벌레는 움직일 수 없게 된다.

	printf("/************** 술취한 바퀴벌레 **************/\n");

	/* 배열의 행과 열의 크기를 입력받는 과정 */
	while (TRUE)
	{
		printf("행과 열의 크기를 2 < row <= 40 / 2 < column <= 40으로 제한한다.\n");
		printf("행(row) 크기 입력: ");	scanf("%d", &m);
		printf("열(col) 크기 입력: ");	scanf("%d", &n);

		// 입력값이 올바르다면 while문 탈출
		if ((n > 2 && m <= 40) && (m > 2 && n <= 40))
			break;
		// 입력값이 올바를 때까지 다시 반복
		else
			printf("범위에 맞지 않는 값이니 다시 입력해주세요.\n");
	}

	/* 바퀴벌레의 시작점을 입력하는 과정 */
	while (TRUE)
	{
		printf("바퀴벌레의 시작점(row, col)을 입력해주세요: ");	scanf("%d %d", &x, &y);

		// 범위를 벗어난다면 범위가 맞을 때까지 while문을 실행한다.
		if (x < 0 || x >= n || y < 0 || y >= m)
		{
			printf("시작 좌표가 타일의 크기를 벗어나니 다시 입력해주세요.\n");
			printf("시작 좌표는 0 <= row < %d, 0 <= col < %d 의 범위로 입력해주세요.\n", n, m);
		}
		// 범위에 맞게 입력되었으므로 while문 탈출
		else
			break;
	}

	/* 배열의 크기에 따라 동적 메모리 할당 */
	tile = (int *)calloc(m * n, sizeof(int));
	// calloc은 malloc과는 다르게 0으로 값을 초기화 해서 메모리를 할당해준다.

	// 처음 시작 위치는 이미 바퀴벌레가 방문했다고 생각하여 1로 설정한다.
	tile[x*n + y] = 1;
	// 개념적으로 방은 2차원 평면 형태로 되어 있지만 
	// 모든 배열은 결국 1차원 배열이다. 1차원 배열을 저장공간으로 활용하기 위해
	// 별도의 주소 연산 x*n + y를 통해 배열에 저장한다.
	// x를 열의 갯수 n과 곱하는 연산에 대해 헷갈리지 않길 바란다.

	// rand() 함수 사용을 위해 srand로 seed값 초기화
	srand((unsigned)time(NULL));

	/* 바퀴벌레의 이동을 반복한다. */
	while (k < 8 && movePossible)
	{
		/* 이동가능한 위치를 선별하는 작업 */
		k = rand() % 8;	// 0 ~ 7 값으로 k를 선정

		// 벌레의 이동할 지점을 미리 지정한다.
		xbug = x + xmove(k);	// 이동 예정인 x좌표
		ybug = y + ymove(k);	// 이동 예정인 y좌표

		// 진짜 이동은 x, y로 표시하기 때문에 아직 진짜로 이동된 건 아니다.
		// 이동 예정인 구간을 먼저 확인하는 것이 먼저 이루어져야하기 때문이다.

		/* 벌레의 이동이 허용범위를 넘었는지 검사하는 과정 */
		while (xbug < 0 || xbug >= m || ybug < 0 || ybug >= n)
		{
			// 허용 범위를 초과하였다면 값을 다시 선정
			// 올바르게 선정될 때까지 이 과정 반복
			k = rand() % 8;
			xbug = x + xmove(k);
			ybug = y + ymove(k);
		}

		// 이동할 예정위치가 올바른 위치이므로 현재 위치를 그 위치로 옮긴다.
		x = xbug;
		y = ybug;

		// 벌레가 방문한 타일 count
		tile[x*n + y]++;

		// 총  움직인 횟수 증가
		totalmove++;
		if ((totalmove + 1) >= 50000)	// 만약 다음 이동 시에 초과할 예정이라면 미리 종료
		{
			printf("벌레가 이동할 수 있는 제한 횟수를 초과하였습니다.\n");
			break;
		}

		// 아직 방문되지 않은 타일이 있는지 검사
		if (emptyTile(m, n))
		{
			// 방문되지 않은 타일이 있으므로 바퀴벌레는 아직 더 움직일 수 있다.
			movePossible = TRUE;
		}
		else
		{
			movePossible = FALSE;	// 모든 타일을 방문했으므로 벌레의 이동을 금지시킨다.
		}

	}

	/* 바퀴벌레의 이동이 모두 끝났으니 tile을 출력한다. */
	/* tile은 개념상 2차원 배열이지만 여기서는 1차원 배열 코드로 작성했다. */
	/* 모든 배열은 결국 1차원 배열이므로 아래와 같이 사용이 가능하다. */
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < n; j++)
		{
			/* 각 좌표에 대해 벌레가 방문한 횟수 출력 */
			printf("%3d ", tile[i * n + j]);

			/* 바퀴가 움직인 전체 횟수를 구한다. */
			total += tile[i * n + j];
		}
		putchar('\n');
	}

	// 바퀴가 각 타일에 움직인 전체 방문 횟수 출력
	printf("total: %d\n", total);
	free(tile);
}

/* 벌레가 이동하지 않은 곳이 있는 지 검사하는 함수 */
int emptyTile(int row_m, int col_n)
{
	int i, j;
	for (i = 0; i < row_m; i++)
	{
		for (j = 0; j < col_n; j++)
		{
			// 방문하지 않은 곳이 있으므로 TRUE를 리턴
			if (tile[i * col_n + j] == 0)
				return TRUE;
		}
	}
	// 모든 곳을 방문했으므로 FALSE를 리턴
	return FALSE;
}

/* 이동 표에 정의된 대로 함수를 정의 */
int xmove(int p)
{
	if (p == 0 || p == 6 || p == 7)
		return -1;
	else if (p == 1 || p == 5)
		return 0;
	else
		return 1;
}

int ymove(int p)
{
	if (p == 4 || p == 5 || p == 6)
		return -1;
	else if (p == 3 || p == 7)
		return 0;
	else
		return 1;
}

/*************************************************
 ** End Line
*************************************************/