본문 바로가기

BOJ 문제풀이

백준 2887 : 행성 터널 https://www.acmicpc.net/problem/2887 행성터널. 최소스패닝트리 문제이다. 간선의 정보를 주는 것이 아니라 정점의 정보(x, y, z 좌표) 를 준다. 따라서 주어진 정점의 정보를 토대로 후보 간선들을 정해야 하는데 정점 N이 100,000 이므로 N^2 연산으로 모든 행성들을 일일이 다 연결시키면 초과가 발생한다. 따라서 간선의 후보를 주어진 조건에 맞게 적절히 설정해야한다.우선 행성과 행성간의 3차원상에서의 거리가 가중치가 아닌x,y,z좌표 중에서 거리가 짧은것 하나만 가중치가 된다. 또한, 모든 행성을 후보로 연결할 필요 없이 x,y,z 좌표중 행성 가까이에 있는 행성들만 후보터널로 사용하면된다. 예시가 다음과 같이 주어졌다 행성번호 1 2 3 4 5 x , y, z 11.. 더보기
백준 1922 : 네트워크 연결 https://www.acmicpc.net/problem/1922 MST(최소스패닝트리)의 가장 기초 문제이다. kruskal 알고리즘 대신 prim 알고리즘을 이용해서 풀어보았다. kruskal 알고리즘은 작은 간선들 부터 차례로 확인해보면서그 간선을 연결하면 cycle이 도는지 확인하는 알고리즘이다.이 때 union-find를 사용하여 재귀적으로 각 정점의 뿌리정점을 정의해주어서로가 연결되어있는지의 여부를 확인한다. 반면, prim 알고리즘은 한 정점을 기준으로 최소 간선을 따라다음 정점를 탐색해나간다. 정점을 하나씩 탐색할때마다새로 탐색한 정점에 연결되어 있던 유효한 간선들을 priority_queue에 넣는다.이는 한정점을 탐색하고 다음 최소 간선은 priority_queue에 넣어놓은 top().. 더보기
백준 10423 : 전기가 부족해 https://www.acmicpc.net/problem/10423 Union-Find를 살짝 응용한 문제.최소 스패닝 트리이되 무조건 모든 노드가 연결이 되는 문제가 아니다. 모든 도시가 연결되어있을 필요는 없고 다만 모든 도시가 발전소와 연결되어 있기만 하면 된다.발전소를 보유하고 있는 도시 가 주어지므로 발전소를 -1로 두었다. 뿌리노드 배열을 -1로 두고 최종적으로 모든 노드의 뿌리노드가 -1이 되면 발전소와 연결이 된 것이다.예시를 참고하자면 1,2,9번 도시가 발전소를 보유하고 있으므로 다음과 같이 설정하고 시작해준다. * vRoot[][1,2,3,4,5,6,7,8,9]-> [-1,-1,3,4,5,6,7,8,-1] ... -> [-1,-1,-1,-1,-1,-1,-1,-1,-1] 이 되면 연결완.. 더보기
백준 1774 : 우주신과의 교감 https://www.acmicpc.net/problem/1774 기본적인 MST 문제이다. 간선이 주어지지 않고 정점의 x,y좌표가 주어졌는데 정점의 개수가 1000개라모든 정점을 연결하는 후보 간선을 뚫어도 N^2연산으로 충분히 가능하다. 단 조금의 차이점은 미리 다리를 놓은 것인데, 이 경우 연결된 간선의UnionFind 에서 merge작업만 수행해주면 된다. 즉 각 노드의 루트노드끼리 병합을 수행해주고 일반적인 Kruskal을 진행하기만하면 된다. 이후 Kruskal을 진행할때 이미 연결한 간선이 나오더라도 이미 root노드가 병합이 되었으므로그냥 무시하고 넘어가기 때문이다. ※ 단, 부동소수점에 관하여..보통 소수점 자리수를 맞출때 setprecision을 사용했다.그러나 이문제에서 setpre.. 더보기
백준 2463 : 비용 https://www.acmicpc.net/problem/2463 쉽지 않은 문제였다... 단 이 과정에서 해당 노드가 속해있는 최상단 뿌리노드 외에 배열을 하나 더 설정해주어야 하는데 그 뿌리노드에 속한 노드들의 개수를저장해주어야 한다. 만약 vRoot[] 가 1,2,3,4,5,6 이면 임의로 groupSize[] 의 변수를 만들고 각 노드그룹이 속한 개수 1,1,1,1,1,1 로 초기화 시켜준다.3과 6이 합병되면 3,6의 vRoot는 3으로 통일이 된다. 그럼 이때 3번노드는 3과 6 두개의 노드를 가지고 잇는 뿌리노드이므로 groupSize[3] = 2가 되어야한다 이는 본래 groupSize[3] 의 값인 1에다가 6의 뿌리노드(6 자신)의 개수 groupSize[6]의 값 1을 합친 2가 되는.. 더보기
백준 3665 : 최종 순위 https://www.acmicpc.net/problem/3665 위상정렬 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 92 93#include #include #include using namespace std; class Node{ public: int inDegree = 0; b.. 더보기
백준 1005 : ACM Craft https://www.acmicpc.net/problem/1005 위상정렬을 할때 단순히 나열하는 것이 아니라이전의 작업 - 예를 들면 해당 건물을 건설하는데 드는 최종 시간을 구함. - 을 모두 마친 후다음 작업을 할때도 쓰인다. 각 건물노드 마다 이전index와 다음 index를 저장하여 이전 index의 건물건설 시간 중가장 오래걸렸던 건설시간을 자신의 건설시간에 더해 현재 건물노드의 건설시간을 설정하는 방식으로구현하였음. 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 .. 더보기
백준 2623 : 음악프로그램 https://www.acmicpc.net/problem/2623 위상정렬 기본문제.항상 어떤 행위의 선행순서가 정해져있는 경우 topological sort를 생각해준다. 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#include #include #include using namespace std; int n, m; class Node{ public: int inDegree = 0; ve.. 더보기

티스토리툴바