[2015_TrendMicro_CTF] (Programming 300) Maze

최종 수정: 2015-10-27

hackability@TenDollar

안녕하세요. Hackability 입니다.

이번 포스팅은 2015 TrendMicro 에서 BlackJack 다음으로 저를 빡(?)치게 했던 Maze 라는 문제 입니다.... -_-;; 왜 해킹 대회에 이런 문제들이 나오는지 ....

Maze (미로찾기) 

먼저 맵 파일이랑 자동으로 돌려서 푼 답에 대한 코드는 다음과 같습니다. 재미로 확인해보세요 :-)

maze_map.zip

maze_answer.txt

먼저 문제자체는 간단합니다.

5 3 0

#####

#G.S#

#####

와 같이 주어 집니다.

첫 줄의 5는 row, 3은 col, 0은 check point의 수 입니다. 

G는 Goal 이고 S는 시작 지점입니다. 이 문제의 정답은 LL 입니다 (왼쪽, 왼쪽 이동)

다른 문제를 보면

7 7 0

#######

# . . . . .  #

##### . #

# . . S . . #

# . #####

# . . G . . #

#######

이러면 정답으로  LLDDRR (왼쪽 두번, 아래 두번, 오른쪽 두번)

뭐 이런식으로 풀면 됩니다. 이런식의 류는 인터넷에 찾아 보면 뭐 알고리즘이나 자료구조 공부 할때 많은 예제들이 있는데 이번 CTF에서는 2가지 룰이 더 추가 됩니다.

한 가지는 check point입니다.

11 11 1

###########

# .# .# .# . . . #

# .# .# .# .###

# . . . . . . . # .#

### .#####.#

# . . G#.# . . .#

### .# .# .# .#

# .# . . .# .# S#

# .# .# .# .###

#C . .# . . . . .#

###########

이런 문제의 경우 바로 G로 가면 되는게 아니라 반드시 맵에 있는 C (Checkpoint)를 모두 먹고 G로 가야지 인정이 됩니다. 따라서 이런 문제는 정답이 UULLDDDDLLUULLDDLLRRUURUU 이 되겠네요

하지막 룰은 Energy 입니다. 맵 중간 중간에 E 라는 것도 있는데 이는 에너지 로써 움직일때마다 에너지가 깍입니다. 초반에 주어지는 에너지는 13000 이며 에너지를 하나 먹을 때 마다 20씩 증가 합니다. 사실 저는 Check point이후, Energy를 먹는 로직도 추가 했어야 했는데 이 로직을 넣지 않아도 에너지가 130인가 남고 깨졌습니다.

일단 이걸로 문제 설명은 대충 끝내고 ... 먼저 한 가지 중요한개 이 맵이 1001개 입니다... 후 ....

초기 230개 까지는 체크 포인트가 없어서 230개 정도 까지는 금방 마무리 했는데 그 다음 부터는 모든 맵에 체크 포인트가 존재 합니다.

그리고 후반부 맵 보시면 ... -_-

15 17 2

###############

# E . . . . . . # . . G# .#

##### .### .# . # .#

# . # . . . . . . . # . . . #

# . #######.#####

# . . C . . . S #. . . . . #

### . # .# .# .#####

# . . . # . # . . . . . . . #

# .# . ####### .###

# . . . # . # .# . . . . . #

### .# . # .#######

# . . . . . # . # . . . . C#

### .# .# .##### . #

# . . . # . . . # .# .# . #

# .# .# . # .# .# .# . #

# .# .# E# . . . . .  . . #

###############

맵 파일은 파일 첨부에 올렷으니 확인하시면 됩니다.

마지막으로 소스에 고려된 사항은 다음과 같습니다.

1. 길 찾기는 Recursive 로 코딩

2. 방금 온길은 다시 돌아 가지 않도록 코딩

3. 만약 내가 오른쪽으로 갓는데 도착지에 도착하지 않고 다시 내가 온길 밖에 없게 된다면 아까 오른쪽으로 결정했던 곳부터 다시 결정을해 왼쪽으로 갈 수 있도록 코딩

4. 체크 포인트를 모두 먹고 Goal 로 가도록 코딩

5. 그리고 답이 나오면 답을 검증 하는 프로그램도 추가

maze.py

 
import sys
 
energy = 13000
 
wall = '#'
start = 'S'
goal = 'G'
checks = 'C'
drink = 'E'
nothing = '.'
maps = []
check = {}
 
def verify(maps, answer, s_x, s_y, e_x, e_y):
 
    for i in range(0, len(answer)):
        ch = answer[i]
 
        if ch == 'L':
            s_x = s_x - 1
        elif ch == 'R':
            s_x = s_x + 1
        elif ch == 'U':
            s_y = s_y - 1
        elif ch == 'D':
            s_y = s_y + 1
 
        if maps[s_y][s_x] == '#':
            return False
 
        if i == (len(answer) - 1):
            if s_y != e_y or s_x != e_x:
            #if maps[s_y][s_x] != 'G':
                return False
 
    return True
        
 
def search(maps, s_x, s_y, e_x, e_y, m_x, m_y, opt, check):
    #print "\t( %d , %d ) -> " % (s_y, s_x),
 
    if s_y == e_y and s_x == e_x:
        return ''
 
    check_str = "%d_%d" % (s_y, s_x)
    
    if check.has_key(check_str):
        #print ' [!] ALREADY WALKED (opt = %d)' % (opt)
        return False
 
    check[check_str] = 1
 
    if opt == 0:
        if (s_x + 1 < m_x) and maps[s_y][s_x+1] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x+1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x+1, s_y, e_x, e_y):
                    return 'R' + res
 
        if (s_x - 1 >= 0) and maps[s_y][s_x-1] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x-1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x-1, s_y, e_x, e_y):
                    return 'L' + res
 
        if (s_y + 1 < m_y) and maps[s_y+1][s_x] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x, s_y+1, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x, s_y+1, e_x, e_y):
                    return 'D' + res
 
        if (s_y - 1 >= 0) and maps[s_y-1][s_x] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x, s_y-1, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x, s_y-1, e_x, e_y):
                    return 'U' + res
    elif opt == 1:
        if (s_x - 1 >= 0) and maps[s_y][s_x-1] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x-1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x-1, s_y, e_x, e_y):
                    return 'L' + res
 
        if (s_y + 1 < m_y) and maps[s_y+1][s_x] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x, s_y+1, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x, s_y+1, e_x, e_y):
                    return 'D' + res
 
        if (s_y - 1 >= 0) and maps[s_y-1][s_x] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x, s_y-1, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x, s_y-1, e_x, e_y):
                    return 'U' + res
        if (s_x + 1 < m_x) and maps[s_y][s_x+1] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x+1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x+1, s_y, e_x, e_y):
                    return 'R' + res
 
    elif opt == 2:
        if (s_y + 1 < m_y) and maps[s_y+1][s_x] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x, s_y+1, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x, s_y+1, e_x, e_y):
                    return 'D' + res
        if (s_y - 1 >= 0) and maps[s_y-1][s_x] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x, s_y-1, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x, s_y-1, e_x, e_y):
                    return 'U' + res
        if (s_x + 1 < m_x) and maps[s_y][s_x+1] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x+1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x+1, s_y, e_x, e_y):
                    return 'R' + res
        if (s_x - 1 >= 0) and maps[s_y][s_x-1] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x-1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x-1, s_y, e_x, e_y):
                    return 'L' + res
 
    elif opt == 3:
        if (s_y - 1 >= 0) and maps[s_y-1][s_x] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x, s_y-1, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x, s_y-1, e_x, e_y):
                    return 'U' + res
        if (s_x + 1 < m_x) and maps[s_y][s_x+1] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x+1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x+1, s_y, e_x, e_y):
                    return 'R' + res
        if (s_x - 1 >= 0) and maps[s_y][s_x-1] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x-1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x-1, s_y, e_x, e_y):
                    return 'L' + res
        if (s_y + 1 < m_y) and maps[s_y+1][s_x] != '#':
            tmp_check = check
            for opt in range(0, 4):
                res = search(maps, s_x, s_y+1, e_x, e_y, m_x, m_y, opt, tmp_check)
                if res != False and verify(maps, res, s_x, s_y+1, e_x, e_y):
                    return 'D' + res
 
    return False
 
for i in range(0, 1001):
    print 
    name = './maze/%04d.map' % (i)
    fd = open(name, 'r')
    data = fd.read().splitlines()
    fd.close()
 
    info = data[0].split(" ")
    x = int(info[0])
    y = int(info[1])
    c = info[2]
 
    for j in range(1, len(data)):
 
        ind_s = data[j].find('S')
 
        if ind_s > -1:
            s_y = j-1
            s_x = ind_s
 
        ind_e = data[j].find('G')
 
        if ind_e > -1:
            e_y = j-1
            e_x = ind_e
 
        maps.append(data[j])
 
    check_point = []
 
    for j in range(1, len(data)):
        for k in range(0, len(data[j])):
            if data[j][k] == 'C':
                check_point.append([j-1, k])
 
    if len(check_point) != 0:
        ''' LOG CHECK POINTS
        fd = open("maze_check_point.txt", "a")
        fd.write("%05d\n" % (i))
        fd.close()
        '''
        pass
 
    print "LEVEL : %4d" % (i)
    for m in maps:
        print m
 
    answer = ''
    check = {}
 
    if len(check_point) == 0:
        print '( %d , %d ) -> ( %d , %d )' % (s_x, s_y, e_x, e_y)
 
        answer = search(maps, s_x, s_y, e_x, e_y, x, y, 0, {})
 
        print 
        print "ANSWER : %s" % (answer)
 
    else:
        print "SHOULD HAVE CHECK POINTS !!!"
 
        skip = []
        check = {}
        
        for j in range(0, len(check_point)):
            if j in skip:
                continue
 
            #print "( %d , %d ) -> ( %d , %d )" % (s_y, s_x, check_point[j][0], check_point[j][1])
 
            check = {}
            for opt in range(0, 4):
                res = search(maps, s_x, s_y, check_point[j][1], check_point[j][0], x, y, opt, {})
                if res != False:
                    break
            print
 
            if res == False:
                print "( %d , %d ) -> ( %d , %d )" % (s_y, s_x, check_point[j][0], check_point[j][1])
 
                print "[WARNING] : %05d" % (i)
                sys.exit(-1)
                break
 
 
            for k in check:
                tmp = k.split("_")
                tmp_y = tmp[0]
                tmp_x = tmp[1]
 
                for l in range(j+1, len(check_point)):
                    if check_point[l][1] == tmp_x and check_point[l][0] == tmp_y:
                        print 'Check point : ( %d , %d )' % (tmp_y, tmp_x)
                        skip.append(l)
 
            answer = answer + res
 
            s_y = check_point[j][0]
            s_x = check_point[j][1]
 
        check = {}
 
        for opt in range(0, 4):
            res = search(maps, s_x, s_y, e_x, e_y, x, y, opt, {})
            if res != False:
                break
 
        answer = answer + res
 
        print
        print "ANSWER : %s" % (answer)
 
    if answer == '':
        print "EMPTY ANSWER : %04d" % (i)
 
    ### ANSWER
    fd = open("maze_answer.txt", "a")
    fd.write("%05d : %s\n" % (i, answer))
    fd.close()
 
    fd = open("maze_submit.txt", "a")
    fd.write("%s\n" % (answer))
    fd.close()
 
    maps  = []
    check = {}
 
 

maze_verify.py

 
 
# READ ANSWER
 
fd = open("maze_answer.txt", "r")
data = fd.read().splitlines()
fd.close()
 
answer = []
for d in data:
    path = d.split(':')[1].strip()
    answer.append(path)
 
for i in range(0, 1000):
    fd = open("./maze/%04d.map" % (i), "r")
    data = fd.read().splitlines()
    fd.close()
 
    maps = []
    s_x = 0
    s_y = 0
    e_x = 0
    e_y = 0
 
    for j in range(1, len(data)):
        ind_s = data[j].find('S')
 
        if ind_s > -1:
            s_y = j-1
            s_x = ind_s
 
        ind_e = data[j].find('G')
        
        if ind_e > -1:
            e_y = j-1
            e_x = ind_e
 
        maps.append(data[j])
 
    check_point = []
 
    for j in range(0, len(maps)):
        for k in range(0, len(maps[j])):
            if maps[j][k] == 'C':
                check_point.append([j, k])
 
 
    walked = []
 
    print "( %d , %d )" % (s_y, s_x)
    verified = 0
 
    walked.append([s_y, s_x])
    for j in range(0, len(answer[i])):
 
        ch = answer[i][j]
 
        if ch == 'L':
            s_x = s_x - 1
        elif ch == 'R':
            s_x = s_x + 1
        elif ch == 'U':
            s_y = s_y - 1
        elif ch == 'D':
            s_y = s_y + 1
 
        print "( %d, %d ) = %c" % (s_y, s_x, maps[s_y][s_x])
        walked.append([s_y, s_x])
            
        if maps[s_y][s_x] == '#':
            print '(%d , %d)' % (s_y, s_x)
            verified = 1
            break
 
        if j == len(answer[i])-1:
            print maps[s_y][s_x]
            if maps[s_y][s_x] != 'G':
                verified = 2
                break
 
 
    # CHECK THE CHECK POINTS
    for ch in range(0, len(check_point)):
        if check_point[ch] not in walked:
            verified = 3
            break
 
    if verified != 0:
        print '[%05d] is (** not **) verified (X) :' % (i),
        if verified == 1:
            print " bricks ..."
        elif verified == 2:
            print " not reached to the [G]oal"
        elif verified == 3:
            print " not consumed the check points"
        continue
 
    print '[%05d] is verified (O)' % (i)
 
 

-_-;; 흠냐;;; 이런 시간 잡아 먹는 문제는 좋지 않음 ... ;;