Algorithm/BOJ
-
[BOJ] 세부(JAVA)Algorithm/BOJ 2021. 2. 3. 20:00
[13905] 세부 www.acmicpc.net/problem/13905 Solution 크루스칼 알고리즘을 사용해 최소신장트리를 만드는 방식을 사용했다. 이 문제에서는 가장 큰 가중치를 구해야 하므로 최대신장트리를 만들면서 edge를 추가할 때 마다 시작점 s와 e가 이어지는지 확인하고 처음으로 이어지는 순간의 가중치가 금빼빼로의 최대 무게가 된다. (PQ에서 큰 가중치를 우선으로 뽑기때문) union-find에서 두 노드의 조상이 같을 때 = 두 노드 간의 경로가 존재함과 같음을 고려해서 푸는 문제이다. 소스코드 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 3..
-
[BOJ] 나만 안되는 연애(JAVA)Algorithm/BOJ 2021. 2. 2. 20:46
[14621] 나만 안되는 연애 www.acmicpc.net/problem/14621 Solution info 배열에 각 노드(대학)의 성별 정보를 저장한 다음 PQ에 성별이 서로 다른 대학을 잇는 간선만 추가해서 최소 신장 트리를 만든다. 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 75 76 77 7..
-
[BOJ] 서강그라운드(JAVA)Algorithm/BOJ 2021. 2. 1. 20:31
[14938] 서강그라운드 www.acmicpc.net/problem/14938 Solution 각 시작점에 대해서 다익스트라로 최단 거리를 구하고 distance 배열에 저장, 수색거리 m 내에 있는 경우만 더해 아이템 개수의 최대값을 구했다. 소스코드 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 ..
-
[BOJ] 어른상어(JAVA)Algorithm/BOJ 2021. 1. 28. 21:44
[19237] 어른상어 www.acmicpc.net/problem/19237 Solution 구현만 잘하면 되는 문제.. 문제를 봤을 때 의 의미가 잘 이해가 안 됐었는데, 현재 방향이 map을 벗어나거나 이동할 수 없는 칸일 때 우선순위표에 나와있는대로 회전해야 한다는 것이다. 그리고 그 기준은 m 마리의 상어 & 상어 방향마다 다르기 때문에 총 (m * 4 * 4) 개의 방향이 주어진다. 소스코드 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 6..
-
[BOJ] 색종이 붙이기(JAVA)Algorithm/BOJ 2021. 1. 27. 15:37
[17136] 색종이 붙이기 www.acmicpc.net/problem/17136 Solution 색종이를 붙일 수 있는 칸에(findDot()) 대해서 1~5 사이즈의 색종이를 붙이고(isValid() & drawing()) 지워가며(removing()) count가 가장 작은 값을 answer에 저장했다. 처음에 접근했던 방식은 map[i][j] 값이 1인 dot들을 List에 넣고, 순서대로 뽑아서 색종이를 붙이는 식으로 구현했는데 이 경우에는 위 6, 7번 예제의 답이 제대로 나오지 않아서 findDot()으로 칸을 찾도록 만들었다. 소스코드 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 ..
-
[BOJ] 빵집(JAVA)Algorithm/BOJ 2021. 1. 25. 15:34
[3109] 빵집 www.acmicpc.net/problem/3109 Solution 간단한 백트래킹 문제인데, 처음에 문제를 보고 고려하지 않아도 될 부분에 대해서 오래 생각해서 시간이 걸렸다. 파이프는 우상향, 우, 우하향으로만 연결될 수 있기 때문에 dfs로 파이프를 연결하다 보면 자연스럽게 우상향으로 파이프는 그려진다. 처음에 잘못 생각했던 부분이 (0~i행에서 시작하는)위에 있는 파이프가 아래로 내려와 그려졌을 때 (i+1~r행)아래행에서 더많이 연결될 수 있음에도 불구하고 연결하지 못하는 경우가 있을거라고 생각했다. dfs 메서드가 다음 칸으로 연결될 수 있을 때만 true를 리턴하도록 만들어서 가장 처음 파이프가 연결된 경우를 제외하고는 map에 그려지지 않고 false를 리턴한다. 반복문 ..
-
[BOJ] 월드컵(JAVA)Algorithm/BOJ 2021. 1. 24. 17:18
[6987] 월드컵 www.acmicpc.net/problem/6987 Solution 국가별로 같은 조에 속한 나라들과 1번씩 총 5번의 경기를 치루기 때문에, matches 배열에 경기 순서를 미리 정의했다. matches 배열에 순서대로 접근하면서 backtracking(count+1) 메서드를 dfs로 호출하고, 옳은 결과를 유지하면서 count==15가 되었을 때 탐색을 종료한다. 총 15 번의 경기만 치루기 때문에 count==15까지 도달했다는 것은 모든 경기가 주어진 결과에 부합한다는 것을 의미한다. 소스코드 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 ..
-
[BOJ] 근손실Algorithm/BOJ 2021. 1. 20. 22:50
[18429] 근손실 www.acmicpc.net/problem/status/18429/3/1 Solution 가장 기본적인 백트래킹 유형이라고 할 수 있다. N은 물론 8이하이고, 모든 순열에 대해 문제의 조건을 충족하는 경우(근손실 없이 N개의 운동 장비를 사용할 수 있는지)만 카운트한다. 소스코드 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 import java.io.BufferedReader;..