백준 알고리즘44 [BOJ]4195번: 친구 네트워크 문제: https://www.acmicpc.net/problem/4195 단순 DFS로 탐색하면 시간초과로 터지는 문제입니다. Union & Find를 통해 해결했습니다. 풀이는 jason님 (https://jason9319.tistory.com/41) 링크를 참고했는데요. 일반 Union & Find 보다 한 단계 더 나아가 자식의 숫자를 저장하고 있어야 합니다. 그러므로 문제가 생기는 부분이 있습니다. 바로 friend1, friend2 로 들어오는 관계가 이미 부모 - 자식 관계인 경우 입니다. BEFORE의 경우 무조건 부모쪽에 더하도록 만들어주었고, AFTER는 부모 - 자식 관계인 경우 부모를 리턴, 부모 - 자식 관계가 아닌 경우 더하도록 만들었습니다. BEFORE 코드가 문제가 되는 이유는.. 2020. 8. 11. [BOJ]5719번: 거의 최단 경로 문제: https://www.acmicpc.net/problem/5719 jaimemin님 블로그의 솔루션을 참고해서 해결했습니다. (https://jaimemin.tistory.com/617) 다익스트라를 진행하게 되면 src => dst 방향으로 최종 노드까지 최소 간선비용으로 갱신이 됩니다. 이 점을 이용해서 다익스트라 진행 중, 최소 간선 비용이거나, 최소 간선 비용과 비용이 같은 경우 before라는 벡터를 선언해 저장해줍니다. //before[NODE]: 최소 간선 비용으로 정점 NODE로 들어오는 정점들을 저장한 벡터 //ex. before[NODE] = {1,2,3,4} 이면 // 1번 정점 => NODE, 2번 정점 => NODE, 3번 정점 => NODE, 4번 정점 => NODE ve.. 2020. 7. 28. [BOJ]17135번: 캐슬 디펜스 문제: https://www.acmicpc.net/problem/17135 시뮬레이션 문제입니다. 아래와 같은 조건들을 문제 요구사항대로 구현해야 합니다. 1. 궁수 배치 2. 궁수가 쏠 타겟 정하기 3. 적들 한 칸씩 내리기 궁수가 쏠 타겟을 정하는 건 우선순위 큐를 사용해서 tuple(거리, X좌표(가로), Y좌표(세로))로 담은 다음 PQ.top()값을 사용하는 것으로 해결하였습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ17135.cc 2020. 7. 22. [BOJ]1916번: 최소비용 구하기 문제: https://www.acmicpc.net/problem/1916 기본 다익스트라 문제입니다. 도시의 개수가 1000개이므로 인접행렬을 사용하든, 인접리스트를 사용하든 상관없습니다. O(ElogV)에 해결할 수 있도록 우선순위큐를 사용해서 문제를 해결하였습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1916.java 2020. 7. 20. 이전 1 ··· 5 6 7 8 9 10 11 다음
