[Programmers]2021 KAKAO BLIND RECRUITMENT: 카드 짝 맞추기(Python)/BFS

https://programmers.co.kr/learn/courses/30/lessons/72415

코딩테스트 연습 - 카드 짝 맞추기

진짜 ... 지금까지 푼 BFS중에 제일 까다롭고 빡치고 어려웠다 ^-^..............

뭘봐

정답률 0.95의 위엄인가 ........

 

어떤 카드를 먼저 뒤집을지 (라이언-어피치-프로도) or (어피치-프로도-라이언) 등 을 먼저 구해주어야 하기 때문에 카드 종류에 맞춰 순열을 구해주고

해당 카드의 짝(라이언A, 라이언B)들 중 어느 카드를 먼저 뒤집을 지도 정해줘야 하기 때문에 순열 만드는게 조금 많이 어려운 문제였다 ....

 

어제부터 거의 8시간 넘게 이문제만 잡고있던 것 같아서 결국은 깔끔하지 못하고 더럽게 풀었다

다음주에 다시 풀어봐야지 .....

#trash code
from collections import deque
from itertools import permutations
from itertools import product

def safe(r,c):
  return r>=0 and r<4 and c>=0 and c<4

card=[]

def makePerm(num, dep, order):
  global card
  arr=[[0,1],[1,0]]
  if dep==len(num):
    card.append([])
    for i in range(len(num)):
      card[-1].append([num[i],arr[order[i]][0]])
      card[-1].append([num[i],arr[order[i]][1]])
    return
  order[dep]=0
  makePerm(num,dep+1,order)
  order[dep]=1
  makePerm(num,dep+1,order)

def solution(board, r, c):
    answer = 4**4
    n=0
    dr=[1,0,-1,0]
    dc=[0,1,0,-1]
    dic={}
    nums=[]
    start=[]

    for i in range(4):
      for j in range(4):
        if board[i][j]!=0:
          num = board[i][j]
          start+=[[board[i][j],abs(r-i)+abs(c-j)]]
          if num>n:n=num
          if dic.get(num)==None:
            dic[num]=0
            nums.append(num)
          else:
            dic[num]=1
          board[i][j]=[num,dic[num]]
    
    start.sort(key=lambda x:x[1])
    inj=[]
    for s in start:
      if s[1]==start[0][1]:
        inj.append(s[0])
    perm=list(permutations(nums, n))
            
    global card
    for p in perm:
      makePerm(list(p),0,[0 for _ in range(n)])

    for order in card:
      if len(card)>48 and order[0][0] not in inj:continue
      q=deque()
      b=[[board[i][j] for j in range(4)]for i in range(4)]
      q.append([r,c,0])
      visit=[[False for _ in range(4)] for _ in range(4)]
      visit[r][c]=True

      o = 0
      while len(q)!=0:
        cur=q.popleft()
        if cur[2]+n*2>=answer:continue
        if b[cur[0]][cur[1]]==order[o]:
          o+=1
          if o==len(order):
            if cur[2]+n*2<answer:answer=cur[2]+n*2
          b[cur[0]][cur[1]]=0
          q.clear()
          visit=[[False for _ in range(4)] for _ in range(4)]

        for i in range(4):
          nr=cur[0]+dr[i]
          nc=cur[1]+dc[i]

          if safe(nr,nc) and not visit[nr][nc]: 
            q.append([nr,nc,cur[2]+1])
            visit[nr][nc]=True

          while safe(nr,nc) and b[nr][nc]==0:
            nr+=dr[i]
            nc+=dc[i]
          
          if not safe(nr,nc):
            nr-=dr[i]
            nc-=dc[i]
          
          if (nr!=cur[0] or nc!=cur[1]) and visit[nr][nc]==False:
            q.append([nr,nc,cur[2]+1])
            visit[nr][nc]=True

    return answer

Kakao's problem is so difficult