미션. 2x2 두 번째 미로

두 번째 미로

이번엔 조금 더 복잡한 미로에 도전해 볼까요?

앗! 왼쪽으로만 돌면 안되는 미로다!

맞습니다.

이 미로는 앞에서 만들어 본 '벽을 만나면 왼쪽으로 돌아라' 햄스터 로봇은 절대로 빠져나갈 수 없는 미로에요.

우리의 목표는 어떤 미로든 척척 빠져나가는 똑똑한 햄스터 로봇이죠?

왜 못 나가는 거지?

첫 번째 미로는 벽을 마주쳤을 때 항상 이런 상황이었습니다.

왼쪽으로 가면 되죠.

그래서 벽을 만나면 왼쪽으로 가라! 라는 규칙으로 움직이게 만들었습니다.

두 번째 미로는 다양한 상황을 만나게 됩니다.

왼쪽으로 가라 알고리즘은 이 미로를 이렇게 움직이게 될 거에요.

갖혀버린거죠!

조금 더 똑똑하게 만들어 봅시다.

하나씩 생각해 봅시다.

1. 왼쪽 길, 오른쪽 길

길이 있는 곳으로 가라.

2. 막다른 길

왼쪽, 오른쪽 다 막혀있다면 되돌아 가라.

3. 갈림길

왼쪽, 오른쪽 둘 다 길이 있다면?

1, 2번 상황은 바로 떠오르는데 갈림길이 어렵죠?

여기서는 간단하게 해 보겠습니다. 양쪽 모두 길이 있다면, 왼쪽으로 가라!

** 참고

갈림길 상황은 햄스터 로봇이 아니라 우리의 똑똑한 머리로도 쉽게 결정하기 힘든 상황입니다.

저 갈림길의 상황에 얼마나 올바른 결정을 하느냐가 얼마나 더 똑똑한가를 결정하게 됩니다.

갈림길 상황을 더 똑똑하게 판단하도록 하고 싶다라는 생각이 들면 컴퓨터 과학의 '그래프 탐색 알고리즘'과 '인공지능'쪽으로 나가게 됩니다.

알고리즘 만들기

이번엔 여러가지 상황을 판단해야 하기 때문에 깊이 고민해서 정리해야 합니다.

3가지 상황에 전부 올바른 판단을 할 수 있게 알고리즘을 만들어 봅시다.

계속 앞으로 가! 가다가 벽이 나오면 먼저 왼쪽에 벽이 있는지 검사해, 벽이 없다면 왼쪽으로 꺾어! 
왼쪽에 벽이 있다면 오른쪽에 벽이 있는지 검사해, 벽이 없다면 오른쪽으로 꺾어!
오른쪽에도 벽이 있다면 뒤로 돌아서 왔던 길로 돌아가!
이걸 계속 반복해! 그러면 나올 수 있어.

복잡해졌죠?

계속 반복해
    만약에 앞에 벽이 있다면
        왼쪽으로 꺾어!
        만약에 앞에 벽이 있다면
            뒤로 돌아! (왼쪽 벽을 바라보는 상태에서 처음의 오른쪽 벽을 바라보게 하기)
            만약에 앞에 벽이 있다면
                오른쪽으로 꺾어! (오른쪽 벽을 바라보는 상태에서 뒤쪽 방향을 바라보게 하기)
    아니면
        앞으로 가!

앞에 벽이 나타나면 조건문으로 판단을 시작합니다.

1. 벽을 만나면 일단 왼쪽 검사. (왼쪽에 벽이 아니면 이후 판단은 하지 않고 왼쪽 길로 감)

2. 왼쪽도 벽이면 뒤로 돌아서 오른쪽 벽 검사. (오른쪽에 벽이 아니면 이후 판단은 하지 않고 오른쪽 길로 감)

3. 오른쪽도 벽이면 오른쪽으로 돌아서 왔던 길로 돌아가기. (막다른 길이라면 왔던 길로 돌아감)