[코드트리] 삼성 SW 역량테스트 | 2018년 상반기 오전 1번 | 이상한 체스

 

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/odd-chess/description

코딩테스트 기출 문제 설명: 이상한 체스 | 코드트리

 

 

• 문제유형 : 백트래킹 
• 난이도 : L12
• 정답률 : 63% 

 

 

풀이 방법

 

 

 

코드 

n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))
row_len = n
col_len = m

# 문제 조건에서 자신의 말의 개수는 최대 8개이므로
move_true = {1:{-1:[]},
            2:{-1:[]},
            3:{-1:[]},
            4:{-1:[]},
            5:{-1:[]},
            6:{-1:[]},
            7:{-1:[]},
            8:{-1:[]}}

# 갈 수 없는 곳 (6) 개수 세기
you = 0


n = 1
for r in range(row_len):
    for c in range(col_len):
        if board[r][c] == 1:
            dr = [0, 0, 1, -1]
            dc = [1, -1, 0, 0]
            for i in range(4):
                move_true[n][(r, c, i)] = [(r, c)]
                next_r = r
                next_c = c 
                while True:
                    next_r += dr[i]
                    next_c += dc[i]
                    if 0 <= next_r < row_len and 0 <= next_c < col_len and board[next_r][next_c] != 6 and ((next_r, next_c) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r, next_c))
                    else:
                        break
            n += 1


        elif board[r][c] == 2:
            dr = [[0, -1], [0, 1]]
            dc = [[-1, 0], [1, 0]]
            for i in range(2):
                move_true[n][(r, c, i)] = [(r, c)]
                next_r1 = next_r2 = r
                next_c1 = next_c2 = c
                while True:
                    next_r1 += dr[0][i]
                    next_c1 += dc[0][i]
                    if 0 <= next_r1 < row_len and 0 <= next_c1 < col_len and board[next_r1][next_c1] != 6 and ((next_r1, next_c1) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r1, next_c1))
                    else:
                        break

                while True:
                    next_r2 += dr[1][i]
                    next_c2 += dc[1][i]
                    if 0 <= next_r2 < row_len and 0 <= next_c2 < col_len and board[next_r2][next_c2] != 6 and ((next_r2, next_c2) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r2, next_c2))
                    else:
                        break
            n += 1

        elif board[r][c] == 3:
            dr = [[-1, -1, 1, 1], [0, 0, 0, 0]]
            dc = [[0, 0, 0, 0], [1, -1, -1, 1]]
            for i in range(4):
                move_true[n][(r, c, i)] = [(r, c)]
                next_r1 = next_r2 = r
                next_c1 = next_c2 = c
                while True:
                    next_r1 += dr[0][i]
                    next_c1 += dc[0][i]
                    if 0 <= next_r1 < row_len and 0 <= next_c1 < col_len and board[next_r1][next_c1] != 6 and ((next_r1, next_c1) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r1, next_c1))
                    else:
                        break

                while True:
                    next_r2 += dr[1][i]
                    next_c2 += dc[1][i]
                    if 0 <= next_r2 < row_len and 0 <= next_c2 < col_len and board[next_r2][next_c2] != 6 and ((next_r2, next_c2) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r2, next_c2))
                    else:
                        break
            n += 1

        elif board[r][c] == 4:
            dr = [[-1, 1, 0, 0], [0, 0, -1, -1], [0, 0, 1, 1]]
            dc = [[0, 0, -1, 1], [1, 1, 0, 0], [-1, -1, 0, 0]]
            for i in range(4):
                move_true[n][(r, c, i)] = [(r, c)]
                next_r1 = next_r2 = next_r3 = r
                next_c1 = next_c2 = next_c3 = c

                while True:
                    next_r1 += dr[0][i]
                    next_c1 += dc[0][i]
                    if 0 <= next_r1 < row_len and 0 <= next_c1 < col_len and board[next_r1][next_c1] != 6 and ((next_r1, next_c1) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r1, next_c1))
                    else:
                        break

                while True:
                    next_r2 += dr[1][i]
                    next_c2 += dc[1][i]
                    if 0 <= next_r2 < row_len and 0 <= next_c2 < col_len and board[next_r2][next_c2] != 6 and ((next_r2, next_c2) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r2, next_c2))
                    else:
                        break

                while True:
                    next_r3 += dr[2][i]
                    next_c3 += dc[2][i]
                    if 0 <= next_r3 < row_len and 0 <= next_c3 < col_len and board[next_r3][next_c3] != 6 and ((next_r3, next_c3) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r3, next_c3))
                    else:
                        break
            n += 1

        elif board[r][c] == 5:
            dr = [[0], [0], [1], [-1]]
            dc = [[1], [-1], [0], [0]]
            for i in range(1):
                move_true[n][(r, c, i)] = [(r, c)]
                next_r1 = next_r2 = next_r3 = next_r4 = r
                next_c1 = next_c2 = next_c3 = next_c4 = c

                while True:
                    next_r1 += dr[0][i]
                    next_c1 += dc[0][i]
                    if 0 <= next_r1 < row_len and 0 <= next_c1 < col_len and board[next_r1][next_c1] != 6 and ((next_r1, next_c1) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r1, next_c1))
                    else:
                        break

                while True:
                    next_r2 += dr[1][i]
                    next_c2 += dc[1][i]
                    if 0 <= next_r2 < row_len and 0 <= next_c2 < col_len and board[next_r2][next_c2] != 6 and ((next_r2, next_c2) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r2, next_c2))
                    else:
                        break

                while True:
                    next_r3 += dr[2][i]
                    next_c3 += dc[2][i]
                    if 0 <= next_r3 < row_len and 0 <= next_c3 < col_len and board[next_r3][next_c3] != 6 and ((next_r3, next_c3) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r3, next_c3))
                    else:
                        break

                while True:
                    next_r4 += dr[3][i]
                    next_c4 += dc[3][i]
                    if 0 <= next_r4 < row_len and 0 <= next_c4 < col_len and board[next_r4][next_c4] != 6 and ((next_r4, next_c4) not in move_true[n][(r, c, i)]):
                        move_true[n][(r, c, i)].append((next_r4, next_c4))
                    else:
                        break
            n += 1
        
        elif board[r][c] == 6:
            you += 1


max_region = 0

for m1 in move_true[1]:
    for m2 in move_true[2]:
        for m3 in move_true[3]:
            for m4 in move_true[4]:
                for m5 in move_true[5]:
                    for m6 in move_true[6]:
                        for m7 in move_true[7]:
                            for m8 in move_true[8]:
                                temp = move_true[1][m1] + move_true[2][m2] + move_true[3][m3] + move_true[4][m4] + move_true[5][m5] + move_true[6][m6] + move_true[7][m7] + move_true[8][m8]
                                max_region = max(max_region, len(set(temp)))

print(col_len*row_len - max_region - you)