아랫글 정답 공개

우선 첫번째 그림을 보자마자 생각나는 것은 이 그림이 미로라는 것입니다.

그렇다면 아래 그림도 분명 미로와 관계되는 것이겠군요.

첫번째 그림을 잘 보니 빨간색 삼각형이 있습니다.

삼각형은 기본적으로 방향성이 있는 무언가를 간단하게 그리기 위해 사용하는 도형입니다.

그러므로 두번째 그림에 있는 삼각형들은 특정 물체가 향하는 방향에 따른 미로에서의 다양한 상황들이 열거되어있는 것임을 알 수 있습니다.

여기서 문제는 이게 어떠한 상황인지 알아내는 것입니다.

몇개의 예시를 보면 L과 R이 적혀있는 화살표가 다른 삼각형을 가리키고 있습니다.

L을 Left, R을 Right라고 생각했을 때 L은 삼각형 좌회전, R은 삼각형 우회전임을 알 수 있습니다.

하지만 단순히 LR이 삼각형의 회전만을 상징하는 것이라면 화살표가 같은 성질의 노드 사이에 2개가 있어야 합니다.

왜 화살표가 한 방향으로만 가리키고 있을지가 의문이군요.

일단 이 의문을 <1>이라고 정의해둡시다.

두번째 그림에 있는 삼각형들 중에서 X 표시가 되어있는 삼각형들이 있습니다.

16번째 삼각형은 사방이 벽이기 때문에 탈출할 수 있는 미로에서 직면 가능한 상황이 아니라는 것을 쉽게 알 수 있습니다만, 그렇다면 나머지 두 삼각형은 왜 X 표시가 되어있을까요?

이 의문을 <2>라고 정의합니다.

<1>와 <2>를 해결해 보기 위하여 삼각형들의 관계를 알아볼 필요가 있습니다.

알기 쉽게 8, 12, 14, 15번째 삼각형을 살펴보도록 합시다.

이 4개의 삼각형들의 3면이 닫혀있으므로 앞이 뚫려있는 15번째 삼각형을 제외하곤 좌회전과 우회전 밖에 할 수 없습니다.

그런데 만약 L과 R이 가능한 상태라면 어째서 우회전을 의미하는 R의 관계가 하나도 없는 걸까요?

12 -> 8 -> 15의 순서대로 삼각형의 움직임을 보면, 미로에서 막다른 길에 도착했을 때 무조건 좌회전만으로 길을 되돌아간다는 것을 확인할 수 있습니다.

다른 식으로 말하자면 막다른 길에서는 절대로 우회전을 하지 않는다는 것입니다.

이 방법을 사용하는 미로 탈출 알고리즘에는 Wall Follower, 즉 우수법(右手法) 혹은 좌수법이 있습니다.

막다른 길에서 절대로 우회전을 하지 않으므로 이 삼각형은 우수법에 의해 움직이고 있음을 알 수 있습니다.

이 사실을 이용하면 <1>과 <2>가 간단하게 해결됩니다.

우수법을 사용하여 미로를 탈출하는 경우 특별한 일이 없는 이상 우회전과 좌회전 관계가 서로 맞물려 있을 수 없습니다.

또한, 우수법을 사용할 경우 오른쪽에 벽이 있고 앞에 길이 있을 경우 벽을 따라 그대로 직진해야 하기 때문에 시작지점이 아닌 이상 11번과 같은 일직선 길에서 좌회전이나 우회전을 할 이유가 없습니다.

<1>과 <2>를 완벽하게 해결했으므로 이 삼각형(로봇)은 우수법을 사용하여 미로를 탈출하는 로봇임을 알게 되었습니다.

다시 1번 그림으로 돌아가도록 하죠.

1번과 2번 그림은 같은 삼각형 표시를 공유하므로 밀접한 관련이 있음이 분명합니다.

따라서 1번 그림에 있는 삼각형도 우수법을 사용하는 미로 탈출 로봇이라고 생각할 수 있습니다.

하지만 1번 그림의 미로를 보면 외벽을 따라 움직이면 탈출가능하리라 한눈에 판단되나, 이 미로는 외벽과 내벽이 분리되어 있을뿐더러 로봇은 내벽에서 출발합니다.

그러므로 우수법을 사용하는 이 로봇은 절대로 파란 깃발 표시가 되어있는 도착 지점에 다다를 수 없습니다.

따라서 정답은

1 : 우수법만으로는 탈출할 수 없는 미로의 예시

2 : 우수법을 사용하는 로봇의 벽에 구조에 따른 행동(회전)들의 관계도 예시

입니다.

참고로 전 과제할 때 용어를 써서

1 : 우수법 알고리즘을 사용하는 로봇이 탈출할 수 없는 미로의 예시

2 : 상태 공간의 일부 중 미로에서 우수법 알고리즘을 사용하는 로봇의 회전에 의한 관계도 예시

라고 썼습니다.

어느정도 맞추셨나요?

우수하군요

우수에 젖었습니다

이런글이있던가

http://www.playxp.com/sc2/balance/view.php?article_id=4873978
참고하세용