지식인에 알고리즘으로 올라와 있길래, 프로그래밍 문제인 줄 알고 풀고 있었는데;; 답 만 올린 분 걸 채택해 갔다는 비사가..

// 옛날에 승려들만 사는 섬이 있었다. 그들 중에는 눈이 빨간 사람과 갈색인 사람이 섰여있다.

// 눈이 빨간 사람은 마법에 걸려있기 때문에 자기의 눈이 빨갛다는 사실을 스스로 깨닫게 되면

// 그날 밤 12시에 목숨을 잃게 된다. 이 섬에 사는 승려들은 서로의 눈 색깔에 대하여 언급하는 것이 절대 금지 되어 있다. 

// 그리고 거을과 같이 비춰볼 수 있는 도구가 없으므로 자신의 눈색을 확인 못한다. 

// 그러던 어느날 이섬에 난파되어 온 선원이 이 섬 규칙을 몰랐으므로 절대로 해서는 안될 말을 내뱉고 말았다.

// “ 모든 스님들을 만나지 못했지만, 당신들 중에서 적어도 1명은 눈이 빨갛군요” 

// 선원은 그 날로 이섬을 떠났지만 남아 있던 승려들은 눈 색깔에 대한 말이 나왔으므로 크게 동요하기 시작했다.

// 그날 밤부터 이 섬에는 무서운 일이 벌어지기 시작했다. 과연 어떤일이 일어났겠는가 ?

//



// 이 이야기의 논리적 추론 과정은 다음과 같습니다.

// 승려가 자신이 빨간 눈 인지를 확인하는 과정이 되지요.

// 승려들은 생각을 합니다. 전부를 보았는데, 빨간 눈이 없다?

// 그렇다는 것은 선원의 말이 거짓이 아니라면, 내가 바로 그 빨간 눈이다!

// 라고 알게 되어 그날 밤 죽게 됩니다.


// 단 여기서 단서를 달았는데, 적어도 1명은 빨갛군요. 이죠? 응용문제에서

// 2명 , 3명이 빨간 경우에 대응하게 합니다. 

// 이 경우에는 스님의 논리적 추론 과정이, 빨간 눈인 누군가를 발견하고 (2명인 경우)

// 쟤가 죽겠구나.. 생각하다가 하루가 지나고, 그가 안 죽은 것을 보고, 어 설마 다른 누가 빨간 눈인가?

// 라고 생각합니다. 그리고 그것이 자신임을 깨닫고, 상대 방도 그렇게 되어 두 명 모두가 이튿날에 죽게 됩니다.


// 3명일 경우에는 개인이 두 명이 빨갛구나 하고 생각합니다만. 실은 3명이죠. 

// 2명인 이들을 보면서, 처음에 그들이 안 죽는 것을 보고, 아 서로가 둘이라서 죽지 않았거니 하고 생각 한 후

// 이튿날 둘이 자신들이 빨갛다는 것을 깨닫고 죽겠구나 싶지만, 죽지 않는 것을 보게 됩니다.

// 거기서 자기 자신도 빨간 눈이다.. 라는 것을 알게 되버리죠.


// 결론적으로 빨간 눈인 사람이 n명일 때 n일 만큼이 걸리게 됩니다.



// 이 이야기에서 우리가 생각해야할 것은 일단 갈색 눈 / 빨간 눈 이라는 플래그의 존재 (변수)

// 승려가 최소 두 명 이상이라는 점. (혼자라면 얘기가 성립하지 않겠죠) (최소 객체 수)

// 날짜 개념이 있다는 점은 카운트의 존재. (변수)

// 사망 플래그. (라고 얘기하니 이상합니다만. 죽었다 라는 개념이 존재하죠)


// 사고의 추론 과정을 알고리즘으로 표현할 수 있어야합니다. 그들은 어떻게 생각할까요?

// 네 즉, 자신 이외의 사람이 빨간 눈인지를 체크하는 탐색. 그리고 그런 경우에 사망으로 이어지는 제어.


// 이상의 것들이 알고리즘을 통해서 문제를 풀기 위한 준비라고 할 수 있겠습니다.


// 승려라는 객체를 표현하기 위해서 언어의 제약은 안두셨으니, 가장 편리한 C++을 사용하여 대응합니다.


#include <iostream>

using namespace std;


// 승려 객체.

class monk

{

public:

// 승려의 생성시 값을 초기화할 생성자

monk()

{

liveFlag = true;

redEye = false;

primaryKey = counter++;

}

// 빨간 눈의 존재 여부를 체크하는 함수. 다른 승려들을 확인한다.

void redEyeChecking(monk* const checkMonk)

{

// 빨간 눈의 수. 

int redEyeCount = 0;

// 인원 수 만큼 체크한다.

for (int i = 0; i < counter; i++)

{

// 빨간 눈을 체크하되 체크하는 것은 자기 자신은 아니어야한다.

if( checkMonk[i].redEye == true && checkMonk[i].primaryKey != this->primaryKey)

{

redEyeCount++;

}

}

// 만일 탐색하였는데도 불구하고 빨간 눈을 발견 하지 못하면, 자신이 빨간 것을 알게 된다.

// 빨간 눈을 발견하였더라도, 2일 째에 그가 살아있다면 자신이 빨간 것이라 생각하게 된다.

// 즉. n명에 대하여 n일의 날짜가 방패역할을 하지만, 날짜가 n값이 되면 깨닫게 되어 그 다음날이 오기전엔 죽습니다.

if(redEyeCount < day)

{

// 즉. 눈의 수 보다 day가 크다면 죽게 됩니다.

death();

}


//이것이 성립할 수 있는 이유는.

// '자신의 눈이 빨갛지 않다' 면, 빨간 대상보다 redCount가 1 높게 됩니다.

// 즉 '내가 빨간 눈이다'라고 인식하는 결론에 도달하기 전에 빨간 자들이 죽기 때문입니다.

// 왜냐하면 빨간 눈이 2명 있고, 갈색 눈이 3명 있을 때. 5명이 서로 중의 빨간 눈을 센다면

// 빨간 눈인 이들은 1명이 빨갛다고 보겠지만, 갈색 눈인 3명은 2명이 빨갛다고 인식하기

// 때문 입니다.

}


void death()

{

// 자신이 빨간 눈이라는 걸 알게되면 죽는다.

cout << primaryKey << "번 승려가 죽었습니다. " << endl;

cout << "그는 " << ((redEye == true)?"빨간":"갈색") << " 눈 입니다." << endl;

liveFlag = false; //사망

}

public:

// 몇 일이 지났는가?

static int day;

// 몇 명의 승려가 존재하는 가? 생성된 승려의 수를 카운팅 하는 변수.

static int counter;


// 해당 승려의 '고유성'을 보장하는 키. 이를 통해서 자신과 타인을 식별한다.

int primaryKey;

// 해당 승려의 빨간 눈 상태 플래그.

bool redEye;

// 해당 승려의 사망 여부를 확인하는 플래그.

bool liveFlag;

};


int monk::counter;

int monk::day;


// 승려의 수 

#define MONK_COUNT 10

void main()

{

monk monkClass[MONK_COUNT];

 

// 이 부분을 주석화 시키면. 전체가 죽는다. (빨간 눈이 없는 거짓 증언의 경우. 스스로가 빨간 눈이라고 오판)

// 빨간 눈의 인수 만큼 생존 일 수가 늘어나고, 죽는다.

monkClass[0].redEye = true;

monkClass[3].redEye = true;

monkClass[5].redEye = true;

monkClass[8].redEye = true;


while(1)

{

// 이곳에서 체크합니다

for (int i = 0; i < MONK_COUNT; i++)

{

monkClass[i].redEyeChecking(monkClass);

}

int LiveCount = 0;

for (int i = 0; i < MONK_COUNT; i++)

{

if(monkClass[i].liveFlag == true)

{

LiveCount++;

}

}


if(LiveCount < MONK_COUNT)

{

// 카운트가 전체 수 보다 적다면 빨간 눈(?)이 죽었다.

// 정상적인 상황에서 승려가 죽었다는 것은, 논리적 결론에 도달한 자들이 사망했다는 의미가 됩니다.

// 따라서 빨간 눈을 가진 자는 죽었다. 고 결론 짓습니다.

// 이는 갈색눈의 사람들일 수도 있습니다. (갈색만 있는 경우. 즉 증언이 거짓이라면. 갈색들이 죽게 됩니다.)

cout << "day : " << monk::day << endl;

cout << "이제 빨간 눈을 한 승려들이 아무도 없습니다." << endl;

exit(0);

}


// 하루가 지났다.

monk::day++;

}

}





'프로그래밍 > 자료구조, 알고리즘' 카테고리의 다른 글

덱(deque)  (0) 2016.01.29
빨간 눈의 승려 문제.  (0) 2015.04.12
자료구조 / 알고리즘  (0) 2015.04.02
Posted by GENESIS8

댓글을 달아 주세요