[프로그래머스][BFS] 혼자 놀기의 달인

혼자 놀기의 달인

프로그래머스

 

 

• 내 풀이
  • 숫자를 key, 상자번호를 value로 하는 딕셔너리 생성
  • 아무 숫자부터 가능한 bfs 돌면서 방문처리하고 한 묶음의 갯수세서 저장
  • 앞에서 방문했던 상자는 다시 방문하지 않음
  • 저장해둔 상자묶음의 갯수 중에 큰 것 2개의 곱

from collections import defaultdict,deque

def solution(cards):
    answer = 0
    n=len(cards)
    
    cards_idx=defaultdict(int)
    for idx,card in enumerate(cards):
        cards_idx[card]=idx+1
    
    result=[]
    visited=[False for _ in range(n+1)]
    for i in range(1,n+1):
        if visited[i]:
            result.append(0)
            continue
            
        queue=deque([i])
        visited[i]=True
        cnt=0
        while queue:
            cur=queue.popleft()
            cnt+=1
            
            nxt=cards_idx[cur]
            if visited[nxt]:
                break
            visited[nxt]=True
            queue.append(nxt)
        
        result.append(cnt)
        
    result.sort(reverse=True)
    answer=result[0]*result[1]
    
    return answer