안녕하십니까? 이번 포스팅에서는 지뢰찾기의 알고리즘에 대해 간단히 설명하겠습니다. 먼저 소스코드를 봅시다.

보시다시피 Createlandmine2 함수가 제법 깁니다. 일단 차례대로 설명드리겠습니다.

- #include <stdlib.h>

srand함수를 사용하기 위해 선언하였습니다.

- #include <time.h>

time함수를 사용하기 위해 선언하였습니다.

- void Createlandmine();

지뢰를 랜덤으로 생성하는 함수입니다.

 - void Createlandmine2();

생성된 지뢰를 이용해 주변 타일들의 값을 생성하는 함수입니다.

 - void Print_arr(void);

만든 타일을 보여주는 함수입니다.

- int arr[9][9];

타일 값을 저장하기 위한 2차원 배열을 전역변수로 선언하였습니다.

이제 main함수를 살펴봅시다.

- srand((int)time(NULL));

srand함수가 나왔습니다. MSDN에서 이 함수를 살펴봅시다.

이 함수는 쉽게 얘기하면 난수 생성을 위한 seed값을 설정해주는 함수입니다.

난수란 특별한 규칙이 없는 임의의 수를 뜻하지요. 즉 랜덤한 값입니다. 

그렇다면 시드는 무엇을 의미할까요? 

기본적으로 컴퓨터에서 난수를 생성한다고 하면 컴퓨터는 내부의 난수표를 이용하여 난수를 생성합니다. 그런데 문제는 이 난수표 자체가 고정되어 있음으로 다음에 다시 난수표를 쓰면 항상 같은 순서로 숫자가 나오게 됩니다.

그래서 이를 방지하기 위해 보통 난수표를 여러개 만들어 놓고 매번 다른 난수표를 읽도록 하는데 이 난수표를 선택하는 기준을 시드라고 합니다. 그런데 또 여기서 문제가 발생하는 것이 이 시드값이 똑같으면 컴퓨터는 똑같은 난수표를 읽게 됩니다. 그러므로 우리는 이 시드값을 랜덤으로 주어 매번 다른 난수표를 읽도록 해야 합니다.

이 시드값을 랜덤으로 주는 방법은 여러가지가 있겠지만 대표적으로 시간을 이용하는 방법이 있습니다. 시간을 이용하여 시드값을 주기위해 여기서는 time함수를 사용하였습니다. time함수를 살펴봅시다.

MSDN의 설명에 의하면 이 time함수는 1970년 1월 1일 자정 이후 경과된 시간을 반환하는 함수라고 나와있습니다.  인자로 받는 timer는 반환값을 저장하는 포인터 변수입니다.  우리는 따로 저장할 필요가 없으므로 매개변수에 NULL값을 주었습니다.

이렇게 하면 시간은 고정될 수 없는 값이므로 시드는 항상 랜덤일 것이고, 시드가 항상 랜덤이므로 시드를 이용해 뽑아내는 난수도 랜덤이 될 것입니다. 추가로 time함수가 반환하는 값은 time_t인데 srand에서 받는 seed값은 int이므로 강제형변환을 이용하였습니다. 다음으로 넘어갑시다.

- printf("지뢰 생성, 지뢰 == 0\n\n");

  Createlandmine();

  Print_arr();

지뢰를 생성하는 구문입니다. 여기서 지뢰는 숫자 0을 의미합니다. 지뢰가 생성되고 나면 결과값을 보기 위해 Print_arr함수를 호출하였습니다. 참고로 함수에 인자값이 없는 이유는 지뢰가 담긴 배열이 전역변수로 선언되었기 때문에 인자로 받을 값이 없기 때문입니다.

- printf("지뢰에 맞게 숫자값 변경\n\n");

  Createlandmine2();

  Print_arr();

생성된 지뢰를 이용하여 주변 타일들의 숫자를 바꾸는 함수입니다. 자신 주변의 타일들중 지뢰 개수가 있는 만큼 자기 타일의 값을 지정해줍니다.

이제 함수들을 살펴봅시다.

- void Createlandmine(void)

  int i,j,count=0;

반복문에 쓰일 i,j변수와 지뢰 개수를 저장할 변수 count를 선언하였습니다.

- while(count != 10)

count가 10이 아니면 반복합니다. 즉 만들어진 지뢰가 10개가 아니면 반복합니다.

- count=0;

count를 0으로 만들어줍니다. 만들어진 지뢰가 10개가 되지 않을 경우 다시 만들기 위해 count를 초기화합니다.

- for(i=0;i<9;i++)

  for(j=0;j<9;j++)

2차원 배열을 조작하기 위해 2중 for문을 돌립니다.

- arr[i][j] = rand()%8;

arr[i][j]에 랜덤값을 집어넣습니다. 이 때 rand함수가 사용되었는데 이 함수를 살펴봅시다.

설명에 따르면 이 함수는 0에서 32767사이에서 랜덤한 정수를 반환한다고 나와 있습니다. 그런데 우리가 원하는 것은 랜덤으로 나오는 지뢰 즉 숫자 0만 필요합니다. 그렇다고 그냥 rand함수를 쓰자니 0이 나올 확률이 매우 적어집니다. 1/32768 확률이니까요. 

초급 지뢰찾기에서는 지뢰는 10개, 타일은 총 81개 입니다. 즉 확률은 약 1/8입니다. 그러므로 우리는 확률을 맞춰주기 위해 rand함수의 결과값에 %8를 붙여 0~7사이의 값만 나오게 하였습니다. 

- if(arr[i][j] == 0)

  count++;

랜덤으로 생성된 값이 0일 경우 count를 하나 증가시킵니다. 즉 지뢰가 생성되었을 경우 지뢰 개수를 의미하는 count를 증가시킨다는 뜻이지요.

이렇게 모든 for문을 다 실행하고 나면 arr에는 각 인덱스에 0~7값이 들어가게 됩니다. 그런데 지뢰를 의미하는 0 값이 10개를 넘거나, 10개가 안될 수 있으므로 while문을 이용하여 지뢰가 딱 10개만 생성되도록 해주었습니다.

자 다음은 이렇게 생성된 지뢰를 이용하여 주변 타일들의 값을 정하는 함수를 설명하겠습니다.

- void Createlandmine2(void)

  int i,j,count;

for문에 사용할 i,j변수와 주변 타일에 존재하는 지뢰 개수를 저장할 count를 선언하였습니다. 이 count의 값에 따라 타일의 숫자값이 바뀝니다.

- for(i=0;i<9;i++)

  for(j=0;j<9;j++)

arr을 조작하기 위해 2중 for문을 돌립니다.

- count = 0;

하나의 타일의 값 지정이 끝나면 당연히 초기화를 시켜주어야 합니다. 뒤쪽에서 처리를 해도 되지만 count를 선언할 때 초기화를 시켜주지 않았기 때문에 앞쪽에서 초기화를 하였습니다.

- if(arr[i][j] != 0)

타일의 값이 지뢰인지 아닌지를 검사합니다. 지뢰이면 if문을 건너뛰고 다음 타일을 검사합니다. 지뢰가 아니라면 값을 지정해주기 위해 if문을 실행합니다.

- if(i == 0)

i가 0일 경우입니다. 여기서 i는 행을 의미하지요.  즉 첫번째 행일 경우를 의미합니다. 첫번째 행일 경우 if문을 실행합니다.

- if(j == 0)

if(arr[i][j+1] == 0)

count++;

if(arr[i+1][j+1] == 0)

count++;

if(arr[i+1][j] == 0)

count++;

j가 0일 경우입니다. 여기서 j는 열을 의미하지요.  즉 첫번째 열일 경우를 의미합니다. 이 if문은  if(i == 0)안에 포함되어 있으므로 첫번째 행의 첫번 째 열 일 경우 if문을 실행하라는 뜻입니다.

그 다음 코드는 주변 타일이 지뢰인지 아닌지를 검사하는 코드입니다. 현재 i는 0이고 j도 0이므로 이 arr]i][j]는 첫번째 줄의 첫번째 열을 의미합니다. 이 타일은 검사할 수 있는 주변 타일이 우측타일, 우측하단타일, 하단타일 이 세개의 타일밖에 없으므로 이 세개의 타일만 검사하도록 하였습니다. 검사를 하여 이 타일들 중에 지뢰를 가진 타일이 나오면 count를 하나 증가시키도록 하였습니다.

- else if(j == 8)

if(arr[i+1][j] == 0)

count++;

if(arr[i+1][j-1] == 0)

count++;

if(arr[i][j-1] == 0)

count++;

j가 8일 경우의 타일 검사 처리부분입니다. i가 0이고 j는 8이므로 첫번째 줄의 마지막 열을 의미합니다. 여기서는 검사할 수 있는 주변 타일이 하단타일, 좌측하단타일, 좌측타일 밖에 없으므로 이 세개의 타일만 검사하여 지뢰일 경우 count를 증가시키도록 하였습니다.

- else

if(arr[i][j+1] == 0)

count++;

if(arr[i+1][j+1] == 0)

count++;

if(arr[i+1][j] == 0)

count++;

if(arr[i+1][j-1] == 0)

count++;

if(arr[i][j-1] == 0)

count++;

 j가 0도 아니고 8도 아닌 값일 때의 타일 검사 처리입니다. 즉 첫번 째 줄의 중간 열(1~7)을 의미합니다. 여기서 검사할 수 있는 주변 타일은 우측타일, 우측 하단 타일, 하단타일, 좌측 하단 타일, 좌측타일 입니다. 

- else if(i == 8)

if(j == 0)

if(arr[i-1][j] == 0)

count++;

if(arr[i-1][j+1] == 0)

count++;

if(arr[i][j+1] == 0)

count++;

이번에는 i가 8일 때의 처리입니다. 즉 마지막 줄을 의미하지요. 마지막 줄에서 j가 0일 때 if문을 실행하므로 마지막 줄의 첫번째 열이라고 보시면 됩니다. 여기서 검사할 수 있는 주변 타일은 상단타일, 상단우측타일, 우측타일 입니다.

- else if(j == 8)

if(arr[i-1][j] == 0)

count++;

if(arr[i-1][j-1] == 0)

count++;

if(arr[i][j-1] == 0)

count++;

이번에는 i가 8이고 j가 8일 때의 처리입니다. 즉 마지막 줄의 마지막 열을 의미하지요. 여기서 검사할 수 있는 주변 타일은 상단타일, 상단좌측타일, 좌측타일 입니다.

- else

if(arr[i][j+1] == 0)

count++;

if(arr[i-1][j+1] == 0)

count++;

if(arr[i-1][j] == 0)

count++;

if(arr[i-1][j-1] == 0)

count++;

if(arr[i][j-1] == 0)

count++;

이번에는 i가 8이고 j가 1~7일 때의 처리입니다. 즉 마지막 줄의 중간열(1~7)을 의미합니다. 여기서 검사할 수 있는 주변 타일은 우측타일, 상단우측타일, 상단타일, 상단좌측타일, 좌측타일 입니다.

else

if(j == 0)

if(arr[i-1][j] == 0)

count++;

if(arr[i-1][j+1] == 0)

count++;

if(arr[i][j+1] == 0)

count++;

if(arr[i+1][j+1] == 0)

count++;

if(arr[i+1][j] == 0)

count++;

이번에는 i가 1~7이고 j가 0일 때의 처리입니다. 즉 중간 줄(1~7)의 첫번째 열을 의미합니다. 여기서 검사할 수 있는 주변 타일은 상단타일, 상단우측타일, 우측타일, 하단우측타일, 하단타일입니다.

- else if(j == 8)

if(arr[i-1][j] == 0)

count++;

if(arr[i-1][j-1] == 0)

count++;

if(arr[i][j-1] == 0)

count++;

if(arr[i+1][j-1] == 0)

count++;

if(arr[i+1][j] == 0)

count++;

i가 1~7이고 j가 8일 때의 처리이므로 중간 줄의 마지막 열을 의미합니다. 여기서 검사할 수 있는 주변 타일은 상단타일, 상단좌측타일, 좌측타일, 하단좌측타일, 하단타일 입니다.

- else

if(arr[i-1][j-1] == 0)

count++;

if(arr[i-1][j] == 0)

count++;

if(arr[i-1][j+1] == 0)

count++;

if(arr[i][j+1] == 0)

count++;

if(arr[i][j-1] == 0)

count++;

if(arr[i+1][j-1] == 0)

count++;

if(arr[i+1][j] == 0)

count++;

if(arr[i+1][j+1] == 0)

count++;

i가 1~7이고 j가 1~7일 때의 처리입니다. 여기서는 주변 타일을 전부 검사할 수 있는 위치이지요. 그렇기에 자신의 타일을 둘러싸고있는 8개의 타일들을 검사합니다. 

코드가 조금 길지만 알고리즘 자체는 간단한 편입니다. 이제 count를 이용하여 타일의 값을 정해주는 부분을 살펴봅시다.

- switch(count)

case 1:

arr[i][j] = 1;

break;

case 2:

arr[i][j] = 2;

break;

case 3:

arr[i][j] = 3;

break;

case 4:

arr[i][j] = 4;

break;

case 5:

arr[i][j] = 5;

break;

case 6:

arr[i][j] = 6;

break;

case 7:

arr[i][j] = 7;

break;

case 8:

arr[i][j] = 8;

break;

default:

arr[i][j] = 9;

break;

count의 값, 즉 주변에 있는 지뢰 개수에 따라 타일의 값을 지정해주는 부분입니다. 지뢰가 하나 있을 경우 값을 1, 2개가 있으면 2,.... 이런식으로 8까지 값을 저장합니다.

여기서 하나 아셔야 할것은 default인데 이 부분은 count값이 1~8이 아니라는 것을 의미합니다. 즉 지뢰가 하나도 없다는 것을 의미하지요. 그러므로 case 0으로 처리할 수도 있습니다. 아무튼 지뢰가 하나도 없을 경우에는 값을 9로 설정합니다. 이 9라는 값은 빈타일을 의미합니다. 

위와 같은 타일을 뜻하는 것이지요. 이렇게 최종적으로 한 타일의 값을 지정해주고 나면 count값은 for문을 다시 시작할 때 초기화됩니다.

자 이제 남은 것은 타일을 출력하는 함수 Print_arr인데 이것은 간단하니 생략하겠습니다. 자 이제 결과를 한 번 봅시다.

위의 배열은 지뢰를 생성한 배열입니다. 지뢰를 의미하는 0이 무작위로 10개 생성된 것을 확인할 수 있습니다.

밑의 배열은 지뢰값을 이용하여 주변타일들의 값을 바꿔준 배열입니다. 제대로 배치가 되었는지 한번 확인해보셔도 좋습니다.

다시 실행하면 랜덤으로 바뀌는 것을 확인할 수 있습니다.

같은 원리로 중급, 고급 난이도의 지뢰도 구현할 수 있습니다.

네 이것으로 포스팅을 마치겠습니다.

Posted by englishmath
,