728x90 반응형 그래프2 [Python] 퍼즐 조각 채우기 퍼즉 조각 채우기문제 출처: 프로그래머스난이도: level 3input size: $n \le 50$ (정사각 격자)(주관) 자료구조: 그래프(주관) 알고리즘: 완전탐색, BFS(주관) 시간복잡도: $O(n^2) = O(V+E)$ ($V=n^2, E=2n(n-1)$) 2개의 정사각 배열이 주어진다. 1은 블록 한 조각을, 0은 빈 공간을 나타낸다.game_board의 빈 공간을 table에 있는 블록을 이용하여 채운다.하나의 공간을 여러 블록으로 채우거나, 작은 블록으로 큰 빈공간을 채우고 나서도 빈 공간이 있으면 안된다.이때 채워지는 블록의 면적을 리턴하면 된다.STEP 1. 서로 같은 블록단순히 면적을 구하는 것은 DFS/BFS를 이용하여 구할 수 있다.그리고 블록은 좌표의 리스트로 나타낼 수 있다... 2024. 7. 3. [Python] 도넛과 막대 그래프 [프로그래머스] 도넛과 막대 그래프문제 출처: 프로그래머스난이도: level 2참고: 2024 KAKAO WINTER INTERNSHIPinput size: $1 \le V, \ E \le 10^6$(주관) 자료구조: 그래프, 리스트(주관) 알고리즘: 그래프, 차수(degree) 개념(주관) 예상 시간복잡도: $O(V+E) = O(10^6)$오랜만에 코테 준비로 프로그래머스 접속했는데, 문제가 굉장히 많아졌다.2년전에 코테 준비할 때 거의 다 푼 것같은데 그새 못푼 문제가 많이 쌓였다. 처음 이 문제를 봤을때 수없이 많은 루프에 정신이 나갔다.처음에 BFS/DFS로 모든 노드를 순회하면서 그래프의 특징을 찾으려 하다가(예: 탐색을 마친 그래프의 노드 개수가 n개고 edge 개수가 n-1이면 막대그래프로 .. 2024. 6. 17. 이전 1 다음 728x90 반응형
