궤도

문제 풀이 할 것이 굉장히 많다... 일단 최대 입력을 보니 브루트포스로 각 섬을 연결하는 모든 다리를 찾아도 될 것 같았다. 그렇다면 각 섬을 연결하는 다리를 어떻게 찾을 것이냐가 문제인데... 각각의 섬을 구분해야 하니 섬마다 다른 숫자로 라벨링하기로 했다. myunji.tistory.com/355 [백준] 2146번 : 다리 만들기 문제 풀이 일단 다른 섬끼리 다리를 이어야 하기 때문에 각각의 섬을 구분해야 한다. 이런식으로 말이다. myunji.tistory.com/280 [백준] 2667번 : 단지번호붙이기 문제 풀이 문제 이름에 왜 띄어쓰기가 myunji.tistory.com 이 문제에서 섬을 구분했던 것과 같은 방법을 쓴다. 0 0 0 0 0 0 2 2 3 3 0 0 0 0 2 2 3 3 0..

문제 풀이 입력이 100,000개까지 들어올 수 있어서 행성 하나하나마다 모두 거리를 구하면 메모리 초과가 발생한다. 그렇다면 MST에 들어올 가능성이 있는 거리만 저장해야 하는데 그걸 도대체 어떻게 알까? 이 부분 때문에 힘들었다. 두 행성을 연결하는 비용을 살펴보자. 보통의 좌표간 거리 구하기 공식이 아니라 x, y, z 좌표의 차이의 절댓값 중 가장 작은 값을 터널 비용으로 한다고 적혀있다. 그럼 문제를 단순화 해서 x좌표만 존재한다고 하자. 그럼 당연히 예제 입력 1에 대한 MST는 (-1) - (10) - (11) - (14) - (19)로 20일 것이다. 그니까 만약에 최종적으로 x좌표의 차이의 절댓값을 MST의 간선으로 사용하게 된다면...그것은 (-1) - (10), (10) - (11),..

문제 풀이 myunji.tistory.com/370 이 문제에서 각 정점이 좌표로 표현되는 정도만 달라졌다고 생각할 수도 있지만...하나 더 생각할 것이 있다. 바로 이미 연결된 정점들이 주어진다는 것이다. 처음엔 초기 연결 정점들이 다 연결가능하겠거니 하고 코드를 작성했다가 아닐 수도 있단 것을 깨달았다. 그니까 간단하게 예를 들자면 4 2 1 1 3 1 2 3 4 3 1 4 4 1 이렇게 입력이 들어와서 이미 1-4를 연결했는데 4-1을 연결하려고 할 수도 있다는 뜻이다. 이 부분만 신경쓰면 크게 어려울건 없다. 소스코드 #include #include #include #include #include using namespace std; typedef pair pp; int v_cnt; //사용한 간..

문제 풀이 최소 신장 트리, 최소 스패닝 트리, MST 등등으로 불리는 문제다. 가중치가 있는 간선이 주어진 그래프가 있을 때 가중치의 합이 가장 작은 트리를 만드는 것인데 트리니까 당연히 사이클이 없을 것이고 정점의 수가 V일 때, 최종 간선의 수는 V-1이 될 것이다. 이러한 MST를 만드는 대표적인 알고리즘은 크루스칼과 프림이 있는데 크루스칼(kruskal)은 유니온 파인드를 이용해 푸는 알고리즘이고 프림은 다익스트라랑 비슷해보여서 많이들 헷갈리지만 아무튼 둘은 다른 알고리즘이다. ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 크러스컬 알고리즘 - 위키백과, 우리 모두의 백과..