knight-move

[너비우선 탐색법으로 작성한 것임]

def list2str(m):

    s=''

    for x in m:

        for y in x:

            s=s+y

    return s

def str2list(s):

    m=[]

    rl=[]

    for x in s:

         rl.append(x)

         if len(rl)==5: 

             m.append(rl)

             rl=[]

    return m

def next_move(s, pos, t, d):

    nl=[]

    iter=[[-2,-1],[-1,-2],[-2,1],[-1,2],[2,1],[1,2],[2,-1],[1,-2]]

    tt=chr(ord(t)+1)

    m=str2list(s)

    for dx,dy in iter:

        x,y=pos[0]+dx,pos[1]+dy

        if 0<=x<5 and 0<=y<5 and m[x][y]=='-':

            mm=str2list(s)

            mm[x][y]=tt

            ss=list2str(mm)

            if ss in d: pass

            else: 

                nl.append([ss,[x,y],tt])

                d[ss]=[pos,tt]

    return nl

dicA={}

q=[]

dicA['A------------------------']=[[0,0],'A']

q.append(['A------------------------',[0,0],'A'])

while q:

    s,pos,t=q.pop(0)

    if t>'x': print(s,pos,t)

    #input('#')

    nl=next_move(s,pos,t,dicA)

    for x in nl:

        q.append(x)

=======================================================================

[깊이우선 탐색]

def list2str(m):

    s=''

    for x in m:

        for y in x:

            s=s+y

    return s

def str2list(s):

    m=[]

    rl=[]

    for x in s:

         rl.append(x)

         if len(rl)==5: 

             m.append(rl)

             rl=[]

    return m

def next_move(s, pos, t, d):

    nl=[]

    iter=[[-2,-1],[-1,-2],[-2,1],[-1,2],[2,1],[1,2],[2,-1],[1,-2]]

    tt=chr(ord(t)+1)

    m=str2list(s)

    for dx,dy in iter:

        x,y=pos[0]+dx,pos[1]+dy

        if 0<=x<5 and 0<=y<5 and m[x][y]=='-':

            mm=str2list(s)

            mm[x][y]=tt

            ss=list2str(mm)

            if ss in d: pass

            else: 

                nl.append([ss,[x,y],tt])

                d[ss]=[pos,tt]

    return nl

i=0

dicA={}

q=[]

dicA['A------------------------']=[[0,0],'A']

q.append(['A------------------------',[0,0],'A'])

while q:

    s,pos,t=q.pop()

    #i+=1

    #if i%100000==0: 

    #    input(t)

    if t>'X':

        print(s,pos,t)

        break

        #input('#')

    nl=next_move(s,pos,t,dicA)

    nl.reverse()

    for x in nl:

        q.append(x)       

=======================================================================

5x5 채스판에서 0.0 에서 knight 가 출발하여 전체 판을 다 여행하는 길을 찾는 프로그램이다.