Study/BOJ (12) 썸네일형 리스트형 BOJ - 최소 스패닝 트리(1197) MST를 찾는 알고리즘 중 union-find를 이용하여 O(E*logE)에 찾을 수 있는 Kruskal algorithm을 이용하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 #include #include #include using namespace std; int V, E; typedef struct graph { int v1; int v2; int cost; }gra.. BOJ - 미네랄(2933) 문제 조건을 잘못 이해하여 헤맸던 문제였다. 1. 벽이 부서진 곳을 기점으로 하여 새로 생성된 cluster를 찾아야 한다. 2. 또한, cluster 중 하나라도 바닥에 닿아 있다면, 그 cluster는 중력의 영향을 받지 않는다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 .. BOJ - 청소년 상어(19236) 이 문제는 상어가 갈 수 있는 칸 중 어떤 칸을 가느냐에 따라 최댓값이 달라지기 때문에 backtracking을 사용해야 하기 때문에 재귀적인 방법으로 풀어야만 한다. 문제의 아이디어는 바로 떠올랐는데 이를 어떻게 코드화 할지가 쉽게 떠오르지 않아서 시간이 좀 걸렸던 것 같다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83.. BOJ - 마법사 상어와 파이어스톰(20058) 2차원 격자가 나오고 인접, 덩어리 등등의 내용이 나오는 것으로 보아 BFS와 DFS를 이용해야겠다고 생각하였다. 그리고 생각한 점이 어떻게 배열을 회전시킬 것인가를 떠올려봤는데, 풀고 나니 간단했는데 생각하는 과정이 너무 오래 걸렸었다. 또한, 얼음이 "동시에" 녹기 때문에 BFS 순서대로 얼음을 녹인다면 바로 틀렸습니다를 받을 것이다. 따라서 map2라는 배열에 녹아야할 칸을 미리 표시해놓고, 한 번에 map에 적용시키는 방법을 사용하였다. 덩어리를 찾을 때는 DFS를 이용하여 가장 큰 덩어리를 찾았다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585.. 이전 1 2 다음
