[ 프로그래머스 ] 위클리 챌린지 3주차_퍼즐 조각
14760 단어 DFSbrute forcepythonDFS
이 문제는 어디서 많이 본것 같았는데 2021년 대기업 코테 기출 문제였다.
무슨 기업인지는 밝힐 수 없지만 킬러문항으로 나왔었다.
그땐 시간 부족해서 못풀었다.
def solution(game_board, table):
n = len(game_board)
def return_piece_list(isGameBoard):
piece_data = 0 if isGameBoard else 1
board = game_board if isGameBoard else table
visit = [[False for _ in range(n)] for _ in range(n)]
newIJ=list(zip([-1,0,1,0],[0,1,0,-1]))
segcheck=lambda x,y: True if 0<=x<n and 0<=y<n else False
def dfs(index,jndex):
temp.append([index,jndex])
visit[index][jndex]=True
for i,j in newIJ:
newI=i+index
newJ=j+jndex
if segcheck(newI,newJ) and not visit[newI][newJ] and board[newI][newJ] == piece_data:
dfs(newI,newJ)
piece_list=[]
for i in range(n):
for j in range(n):
if board[i][j] == piece_data and not visit[i][j]:
temp=[]
dfs(i,j)
piece_list.append(temp)
return piece_list
def rotate_piece_list_and_normalize(piece_list):
real_list=[]
def normalize(piece):
small_i,small_j=sorted(piece)[0]
return sorted([ [i-small_i,j-small_j] for i,j in sorted(piece)])
def rotate_piece(piece):
return sorted([ [j,-i] for i,j in piece])
for piece in piece_list:
one = normalize(piece)
two = normalize(rotate_piece(one))
three = normalize(rotate_piece(two))
four = normalize(rotate_piece(three))
real_list.append([one,two,three,four])
return real_list
game_piece_list=rotate_piece_list_and_normalize(return_piece_list(True))
table_piece_list=rotate_piece_list_and_normalize(return_piece_list(False))
sum=0
def isSame(game_piece,table_piece):
for i in game_piece:
for j in table_piece:
if i==j:
return True
return False
for game_piece in game_piece_list[:]:
for table_piece in table_piece_list[:]:
if isSame(game_piece,table_piece) and game_piece in game_piece_list and table_piece in table_piece_list:
game_piece_list.remove(game_piece)
table_piece_list.remove(table_piece)
sum+=len(game_piece[0])
return sum
Author And Source
이 문제에 관하여([ 프로그래머스 ] 위클리 챌린지 3주차_퍼즐 조각), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ha-mulan/프로그래머스-위클리-챌린지3주차퍼즐-조각저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)