2017 아 리 내 추 필 시험 – 알고리즘 엔지니어

2017 아 리 내 추 필 시험 – 알고리즘 엔지니어

'''
               ，           。                 ，           1  ，               
32 34 7 33 21 2 
13 12 3 11 26 36 
16 30 22 1 24 14 
20 23 25 5 19 29 
27 15 9 17 31 4 
6 18 8 10 35 28 
                ，        ，      ，  ，       ，              ，    。       ，          25-22-3。
  30-23-20-16-13-12-3       。            。
'''
'''
     :
  ：         ,            ,       s                 s-1    .                   .
    ：
1. P                    (      0)
2.s=1,      1  
3.                      ,          1
4. s=2  ,          ( =0   ),      
5.    1：                      (s-1)    
6.    2：       1,       (s-1)   ,                  ，                 ;             ,      (s+1)   
7.  3-6 ,               .
'''

def function(L, row, col):
    maxlen = 0
    P = [[0 for i in range(col)] for j in range(row)]
    time = row * col
    print('time = ',time)
    N = []
    s = 1
    for i in range(row):
        for j in range(col):
            ok = True
            if i-1 > 0 and L[i][j] > L[i-1][j]: 
                ok = False
            if i+1 < row and L[i][j] > L[i+1][j]: 
                ok = False
            if j-1 > 0 and L[i][j] > L[i][j-1]:
                ok = False   
            if j+1 < col and L[i][j] > L[i][j+1]:
                ok = False  
            if ok:
                P[i][j] = s
                N.append([i,j])  
                time -= 1
    print('P = ',P)
    s += 1
    while time > 0:
        print(time)
        NowN = []
        for i in range(len(N)):
            NowN.append(N[i])
        print('s = ',s)
        print('NowN = ',NowN)
        for l in NowN:
            i = l[0]
            j = l[1]
            print('i = {}, j = {} '.format(i, j)) 

            if i-1 >= 0:
                i_n = i-1
                j_n = j
                print('i-1   ')
                print('i_n = {}, j_n = {} '.format(i_n, j_n)) 

                if(P[i_n][j_n] == 0):
                    ok = True
                    if i_n-1 >= 0 and L[i_n][j_n] > L[i_n-1][j_n] and P[i_n-1][j_n] == 0: 
                        ok = False
                    if j_n-1 >= 0 and L[i_n][j_n] > L[i_n][j_n-1] and P[i_n][j_n-1] == 0:
                        ok = False   
                    if j_n+1 < col and L[i_n][j_n] > L[i_n][j_n+1] and P[i_n][j_n+1] == 0:
                        ok = False  
                    if ok:
                        P[i_n][j_n] = s
                        N.append([i_n,j_n])  
                        time -= 1
            if i+1 < row:
                i_n = i+1
                j_n = j 
                print('i+1   ')
                print('i_n = {}, j_n = {} '.format(i_n, j_n)) 
                if(P[i_n][j_n] == 0):
                    ok = True
                    if i_n+1 < row and L[i_n][j_n] > L[i_n+1][j_n] and P[i_n+1][j_n] == 0: 
                        ok = False
                    if j_n-1 >= 0 and L[i_n][j_n] > L[i_n][j_n-1] and P[i_n][j_n-1] == 0:
                        ok = False   
                    if j_n+1 < col and L[i_n][j_n] > L[i_n][j_n+1] and P[i_n][j_n+1] == 0:
                        ok = False  
                    if ok:
                        P[i_n][j_n] = s
                        N.append([i_n,j_n])  
                        time -= 1
            if j-1 >= 0:
                i_n = i
                j_n = j-1 
                print('j-1   ')
                print('i_n = {}, j_n = {} '.format(i_n, j_n)) 
                if(P[i_n][j_n] == 0):
                    ok = True
                    if i_n-1 >= 0 and L[i_n][j_n] > L[i_n-1][j_n] and P[i_n-1][j_n] == 0: 
                        ok = False
                    if i_n+1 < row and L[i_n][j_n] > L[i_n+1][j_n] and P[i_n+1][j_n] == 0: 
                        ok = False
                    if j_n-1 >= 0 and L[i_n][j_n] > L[i_n][j_n-1] and P[i_n][j_n-1] == 0:
                        ok = False     
                    if ok:
                        P[i_n][j_n] = s
                        N.append([i_n,j_n])  
                        time -= 1
            if j+1 < col:
                i_n = i
                j_n = j+1 
                print('j+1   ')
                print('i_n = {}, j_n = {} '.format(i_n, j_n)) 
                if(P[i_n][j_n] == 0):
                    ok = True
                    if i_n-1 >= 0 and L[i_n][j_n] > L[i_n-1][j_n] and P[i_n-1][j_n] == 0: 
                        ok = False
                    if i_n+1 < row and L[i_n][j_n] > L[i_n+1][j_n] and P[i_n+1][j_n] == 0: 
                        ok = False   
                    if j_n+1 < col and L[i_n][j_n] > L[i_n][j_n+1] and P[i_n][j_n+1] == 0:
                        ok = False  
                    if ok:
                        P[i_n][j_n] = s
                        N.append([i_n,j_n])  
                        time -= 1

            N.remove([i,j])
        s += 1
    return(P,s-1)

L = [[32, 34, 7, 33, 21, 2],
[13, 12, 3, 11, 26, 36], 
[16, 30, 22, 1, 24, 14], 
[20, 23, 25, 5, 19, 29], 
[27, 15, 9, 17, 31, 4], 
[6, 18, 8, 10, 35, 28] ]   
(P,s) = function(L, 6, 6)
print('P = ',P)
print('s = ',s)

출력 결과: P = [4, 5, 2, 3, 2, 1], [3, 2, 1, 2, 5, 6], [4, 7, 2, 1, 4, 1, 1, 1], [5, 6, 7, 2, 3, 4], [6, 3, 2, 3, 4, 1], [1, 4, 1, 2, 5, 2] s = 7