반응형 BFS4 백준 1430번 - 공격 (C++) 문제 해결 방법 BFS를 통하여 풀 수 있는 평범한 문제라고 생각한다. 적 위치부터 너비 기반 탐색을 시작하여며 탑을 발견하였다면 n번에 걸쳐서 발견한 탑인지에 따라 에너지/2^n를 누적해주어 탑끼리의 에너지 전달을 구현하였다. BFS방식은 2차원 벡터를 통하여 3,0(Vec[3][0])을 기준으로 2거리 이내의 탑을 찾는다고 한다면, x를 기준으로 최대, 최소인 Vec[1] 부터 Vec[5]까지만 순회하며 해당 좌표가 두 점 사이의 공식(sqrt(pow(XX - i, 2) + pow(YY - j, 2)))을 통하여 거리가 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.. 2021. 8. 7. 백준 2206번 - 벽 부수고 이동하기 (C++) 문제 해결 방법 일반적이지 않은 최단거리 문제라 BFS를 이용하여 구현하였으며, visit를 3차원 배열로 선언하여서 [좌표][좌표][벽을 뚫고 여기까지 도착했는가?]를 표시하였다. [][][1] 이면 해당 좌표까지 도착하는 길에 벽을 뚫고 온 것이고 [][][0]이라면 해당 좌표까지 오는 길에 벽을 뚫고 오지 않은 것. 또한, queue에 좌표뿐 아니라 해당 경로에서 벽을 뚫고 왔는지에 대한 변수 또한 필요하여 총 3개의 변수를 이용하여 queue를 구성하였다. 아쉬웠던 점 없음 코드 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 .. 2021. 7. 30. 백준 2606번 - 바이러스 (C++) 문제 해결 방법 링크(pair형)를 담는 벡터에 링크를 모두 담은 후, BFS방식을 사용하여 탐색함. 아쉬웠던 점 링크를 그냥 벡터에 넣어서 그래프 탐색 과정에서 모든 링크를 순회하다 보니 복잡도가 올라갔다. 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 #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); co.. 2021. 7. 9. 백준 16234번 - 인구 이동 (C++) 문제 해결 방법 : 시작점부터 배열을 BFS방식으로 하나의 국가로 묶어서 인구 이동을 처리하였다. -> 이후 반복. 아쉬운 점 : 시간이 너무 많이 걸렸고, 코드도 비 효율적이며, 가독성마저 구리다. 상위권은 한자릿수던데 난 700ms... 코드 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.. 2021. 5. 7. 이전 1 다음 반응형
