http://www.pythonchallenge.com/pc/hex/ambiguity.html
접속을 하면 아래와 같인 미로 이미지가 나온다. 오른쪽 상단을 입구로 해서 왼쪽 하단의 출구로 나가는 미로찾기를 작성해야 하는 것으로 보인다.
미로찾기 알고리즘은 여러 알고리즘이 있으나 가장 간단한 좌수법(왼손으로 벽짚고 따라가기) 으로 작성하여 보았다. 좌수법의 알고리즘 원리는 아래와 같다.
1. 왼쪽이 비어있으면 왼쪽으로 먼저 간다.
2. 왼쪽이 막혀있고 위쪽이 비어있으면 위쪽으로 간다.
3. 왼쪽, 위쪽이 막혀있고 오른쪽이 비어있으면 오른쪽으로 간다.
4. 전부 막혔을 경우, 전부 비어있을 경우 아래로 간다.
5. 왼쪽이 비게되면 전부 비어있더라도 왼쪽 먼저 간다.
6. 현재 진행 방향이 존재하기 때문에 위, 아래, 왼쪽, 오른쪽 등 모든 경우에 대해 조사한다.미로를 푼 이미지는 아래와 같다.
무슨 지도같아 보이기도 하고 여기서 어떻게 해야 할지 몰라 지인분께 힌트를 구하니 "저 이미지의 경로를 따라가면 답이 나온다." 라고 하였다.
그래서 기존 미로 이미지에서 입구에서 출구까지 나오는 길에서의 RGB 값을 구하여 보니 R 값만 보이는 것을 확인할 수 있었고 해당 값만 따로 모아서 저장하여 보니 ZIP 파일임을 확인할 수 있었다. ZIP 파일을 풀어보면 아래 이미지가 나온다.
아래는 풀이코드 이다. 코드가 너무 엉망이라도 이해 부탁 :-p
#!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'