Algorithm
-
[BOJ] 도시 분할 계획Algorithm/BOJ 2020. 10. 19. 20:50
[1647] 도시 분할 계획 www.acmicpc.net/problem/1647 Solution 마을을 정점으로 하는 최소 간선 트리(MST)를 만드는 문제 전체 마을을 두 개로 분할해야하기 때문에 간선의 개수가 N-2개가 되는 순간 종료하면 된다. 소스코드 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 import jav..
-
[BOJ] 녹색 옷 입은 애가 젤다지?Algorithm/BOJ 2020. 10. 19. 19:56
[4485] 녹색 옷 입은 애가 젤다지? www.acmicpc.net/problem/4485 Solution 각 동굴의 칸을 정점으로 정의하고, 다익스트라를 활용했다. map의 (0, 0)을 다익스트라의 시작점으로 정하고 (n-1, n-1)칸 까지의 최단 거리를 구했다. 소스코드 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 8..
-
[BOJ] 치즈Algorithm/BOJ 2020. 10. 19. 14:56
[2636] 치즈 www.acmicpc.net/problem/2636 Solution map의 (0, 0) 위치에서 치즈의 개수가 0이 될 때 까지 bfs 함수를 실행한다. 팀색 중에 치즈의 바깥부분, 1인 부분을 찾으면 map에서 0으로 바꾸고 visited 배열에 방문표시를 해준다. 한 번의 bfs 탐색마다 1씩 증가하는 시간을 answer 변수에 담고, 마지막 치즈 개수는 count 변수에 bfs 함수가 끝날 때 마다 업데이트 한다. 소스코드 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 5..
-
[BOJ] 후보 추천하기Algorithm/BOJ 2020. 10. 4. 16:05
[1713] 후보 추천하기 www.acmicpc.net/problem/1713 Solution 문제에서 주어진 조건대로 구현하면 되는 문제 idx, like, order 속성을 가진 Student 객체를 만들어 추천받은 순서 대로 우선순위 큐에 넣었다. 우선순위 큐의 정렬 조건은 like, 추천수가 작은 Student가 먼저 빠져나오고 추천수가 같은 경우에는 order, 들어간 순서가 오래된 Student가 먼저 나오도록 했다. 추천받을 학생이 이미 우선순위 큐에 들어있는 경우에는 해당 학생은 like, 추천수를 업데이트 한 후 다시 넣어줬다. 우선순위 큐에 들어있는 Student를 뽑지 않고 큐 들어있는 상태에서 like를 업데이트 하면 큐의 정렬 조건에 반영되지 않으므로 모든 Student 객체를 뽑..
-
[BOJ] 다리 만들기 2Algorithm/BOJ 2020. 9. 8. 19:46
[17472] 다리 만들기 2 www.acmicpc.net/problem/17472 Solution 다리 만들기 2 문제는 기존의 다리 만들기 문제와 세 가지 다른점이 있다. 다리의 모양에 제한이 있는 것과 한 개의 다리가 아닌 모든 섬을 연결하는 다리를 만드는 것 그리고 다리의 길이는 최소 2 이상이어야 한다는 것이다. 모든 섬을 연결하는 최소 비용의 다리를 만든다는 점에서 Spanning Tree idea를 떠올려야 한다. 먼저 각각의 섬을 구분하기 위한 numbering 작업을 수행한다. MST(최소 신장 트리)를 구하기 위해 크루스칼 알고리즘을 사용했다. map의 모든 cell에 대해 DFS로 섬과 섬을 연결하는 비용(거리)을 구해 우선순위 큐에 넣는다. 이때 주의할 점은 다리는 'ㅡ' 혹은 'l..
-
[BOJ] 다리 만들기Algorithm/BOJ 2020. 9. 7. 18:33
[2146] 다리 만들기 https://www.acmicpc.net/problem/2146 Solution 먼저 각 섬을 구분하기 위한 Numbering 작업을 하고 map[][]의 모든 cell에 대해 바다가 아니면 BFS 탐색을 한다. BFS 탐색을 통해 섬의 끝부분에서 다른 섬까지의 최소값을 answer에 저장한다. 소스코드 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..
-
[BOJ] 게리맨더링Algorithm/BOJ 2020. 9. 6. 19:48
[17471] 게리맨더링 https://www.acmicpc.net/problem/17471 Solution permutation 함수로 N개 구역을 두 선거구로 나눈다음 나뉘어진 선거구에 대해 인접한 선거구인지 체크하는 isConnected 함수를 호출한다. 각 선거구에 대해 dfs로 탐색했을 때 모든 지역을 방문했다면 인접한 선거구이다. answer에 인구 차이의 최솟값을 저장한다. 소스코드 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 6..
-
[BOJ] 파이프 옮기기 1Algorithm/BOJ 2020. 9. 6. 16:12
[17070] 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 Solution (0,1) 위치에서 부터 이동할 수 있는 모든 경우를 dfs로 탐색 대각선 파이프로 이동하는 경우에 빈칸이어야 하는 조건을 미리 고려해야한다. 소스코드 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..