The Python Challenge – Level 24

http://www.pythonchallenge.com/pc/hex/ambiguity.html

접속을 하면 아래와 같인 미로 이미지가 나온다. 오른쪽 상단을 입구로 해서 왼쪽 하단의 출구로 나가는 미로찾기를 작성해야 하는 것으로 보인다.

사용자 삽입 이미지
미로찾기 알고리즘은 여러 알고리즘이 있으나 가장 간단한 좌수법(왼손으로 벽짚고 따라가기) 으로 작성하여 보았다. 좌수법의 알고리즘 원리는 아래와 같다.

1. 왼쪽이 비어있으면 왼쪽으로 먼저 간다.
2. 왼쪽이 막혀있고 위쪽이 비어있으면 위쪽으로 간다.
3. 왼쪽, 위쪽이 막혀있고 오른쪽이 비어있으면 오른쪽으로 간다.
4. 전부 막혔을 경우, 전부 비어있을 경우 아래로 간다.
5. 왼쪽이 비게되면 전부 비어있더라도 왼쪽 먼저 간다.
6. 현재 진행 방향이 존재하기 때문에 위, 아래, 왼쪽, 오른쪽 등 모든 경우에 대해 조사한다.

미로를 푼 이미지는 아래와 같다.

사용자 삽입 이미지
무슨 지도같아 보이기도 하고 여기서 어떻게 해야 할지 몰라 지인분께 힌트를 구하니 "저 이미지의 경로를 따라가면 답이 나온다." 라고 하였다.

그래서 기존 미로 이미지에서 입구에서 출구까지 나오는 길에서의 RGB 값을 구하여 보니 R 값만 보이는 것을 확인할 수 있었고 해당 값만 따로 모아서 저장하여 보니 ZIP 파일임을 확인할 수 있었다. ZIP 파일을 풀어보면 아래 이미지가 나온다.

사용자 삽입 이미지
아래는 풀이코드 이다. 코드가 너무 엉망이라도 이해 부탁 :-p
[code]#!c:\python25\python.exe
# –– coding: utf-8 –
import Image

maze = Image.open(‘maze.png’)
size = maze.size
tmp = Image.new(‘RGB’, size, ‘black’)

”’
– 미로찾기 좌수법 알고리즘 –
왼쪽이 비어있으면 왼쪽 먼저,
왼쪽이 막혀있고 위쪽이 비어있으면 위쪽,
왼쪽, 위쪽이 막혀있고 오른쪽이 비어있으면 오른쪽,
전부 막혔을 경우, 전부 비어있을 경우 아래로 간다.
왼쪽이 비게되면 전부 비어있더라도 왼쪽 먼저 간다.

현재 진행 방향이 존재하기 때문에 위, 아래, 왼쪽, 오른쪽등
모든 경우에 대해 조사한다.
”’

def check_left(im, x, y, color):   # 좌
    data = im.getpixel( (x-1, y) )

    if data[1] == color:
        return 1
    else:
        return 0

def check_right(im, x, y, color):   # 우
    try:
        data = im.getpixel( (x+1, y) )
 
        if data[1] == color:
            return 1
        else:
            return 0
    except:
        return 0

def check_forward(im, x, y, color):   # 상
    try:
        data = im.getpixel( (x, y-1) )
    
        if data[1] == color:
            return 1
        else:
            return 0
    except:
        return 0

def check_backward(im, x, y, color):   # 하
    data = im.getpixel( (x, y+1) )
 
    if data[1] == color:
        return 1
    else:
        return 0

def check(im, now, x, y, color):
    if now == ‘up’:
        left = check_left(im, x, y, color)
        right = check_right(im, x, y, color)
        up = check_forward(im, x, y, color)

        if left == 1:
            now = ‘left’
            x -= 1
        elif left == 0 and up == 1:
            now = ‘up’
            y -= 1
        elif left == 0 and up == 0 and right == 1:
            now = ‘right’
            x += 1
        elif left == 0 and up == 0 and right == 0:
            now = ‘down’
            y += 1

    elif now == ‘down’:
        left = check_right(im, x, y, color)
        right = check_left(im, x, y, color)
        up = check_backward(im, x, y, color)

        if left == 1:
            now = ‘right’
            x += 1
        elif left == 0 and up == 1:
            now = ‘down’
            y += 1
        elif left == 0 and up == 0 and right == 1:
            now = ‘left’
            x -= 1
        elif left == 0 and up == 0 and right == 0:
            now = ‘up’
            y -= 1

    elif now == ‘right’:
        left = check_forward(im, x, y, color)
        right = check_backward(im, x, y, color)
        up = check_right(im, x, y, color)

        if left == 1:
            now = ‘up’
            y -= 1
        elif left == 0 and up == 1:
            now = ‘right’
            x += 1
        elif left == 0 and up == 0 and right == 1:
            now = ‘down’
            y += 1
        elif left == 0 and up == 0 and right == 0:
            now = ‘left’
            x -= 1

    elif now == ‘left’:
        left = check_backward(im, x, y, color)
        right = check_forward(im, x, y, color)
        up = check_left(im, x, y, color)

        if left == 1:
            now = ‘down’
            y += 1
        elif left == 0 and up == 1:
            now = ‘left’
            x -= 1
        elif left == 0 and up == 0 and right == 1:
            now = ‘up’
            y -= 1
        elif left == 0 and up == 0 and right == 0:
            now = ‘right’
            x += 1

    return now, x, y

def extract():
    x = 639         # 시작 x 좌표
    y = 0           # 시작 y 좌표
    now = ‘down’    # 시작 시 진행방향
    zipdata = ”
    count = 0
    while 1:
        count += 1
        data = maze.getpixel( (x, y) )
       
        if count % 2 == 0:
            zipdata += chr(data[0])
           
        now, x, y = check(tmp, now, x, y, 222)

        if y == 640:
            break

    zipfile = open(‘output.zip’, ‘wb’)
    zipfile.write(zipdata)
    zipfile.close()

def main():
    x = 639         # 시작 x 좌표
    y = 0           # 시작 y 좌표
    now = ‘down’    # 시작 시 진행방향
   
    while 1:
        tmpx = x
        tmpy = y
        tmp.putpixel( (x, y), (222, 222, 222, 222) )

        now, x, y = check(maze, now, x, y, 0)
       
        print ‘(‘ + str(x) + ‘, ‘ + str(y) + ‘)’

        data = tmp.getpixel( (x, y) )
        if data[1] == 222 and data[2] == 222:
            tmp.putpixel( (tmpx, tmpy), (0, 0, 0, 0) )

        else:
            tmp.putpixel( (x, y), (222, 222, 222, 222) )

        if y == 640:
            extract()  # 저장해둔 길따라 다시 최단 거리로 재탐색
            tmp.save(‘output.png’)
            tmp.show()

            break

if name == ‘main‘:
    print ‘[+] Start’
    main()
    print ‘[+] End’
[/code]

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다