알고리즘 MST 과제

[Sabro98]

Minimum Spanning Tree 파트 관련 과제 (난이도 순서)

필수
[1] [2] [3]

위 문제들을 스터디 시간에 아래와 같은 토론을 진행하겠습니다.

1. 어떤 부분이 어려운지?
2. 어떻게 해결하는지?
3. 시간복잡도는?

스터디 전까지 모두 풀어와주세요!

스터디 시작 전까지 Issue에 자신만의 답을 남겨주세요!

만약 못풀겠으면, 구글에 검색하더라도 꼭! 풀어와주세요

톡방에 전달 부탁드립니다~

---

@tjdeo1102 @rkdbq @jys-jeong @bootkorea @tlstmdgjs

[jys-jeong]

1-1,2 크루스칼 알고리즘을 사용하여 풀면 어렵지 않다
1-3 O(ElogE) (E는 간선)

2-1 bfs와 MST를 어떤 식으로 응용 해야 할지 몰랐다.
2-2 bfs를 이용하여 각 정점 간의 가중치를 구하고 크루스칼 알고리즘을 이용하여 모든 로봇의 움직인 횟수를 구한다.
2-3 O(N^2)이라고 생각한다(N는 열쇠 갯수)

3-1,2 프림 알고리즘을 사용하여 풀면 풀 수 있다.
3-3 O(ElogE) (E는 간선)

[rkdbq]

[1]

1. 어떤 부분이 어려운지?

강의의 MST와 거의 유사하므로 문제 자체는 어렵지 않았습니다.
크루스칼 알고리즘을 완전히 이해하는 데에 시간을 많이 투자했습니다.

2. 어떻게 해결하는지?

크루스칼 알고리즘에서 같은 그룹으로 만들 때 문제의 요구(사심 경로의 특징)에 맞도록 조건을 수정해 해결했습니다.

3. 시간복잡도는?

Union-find가 최악의 경우 O(N), STL sort()가 O(NlogN)의 시간복잡도를 가지므로 최종적으로 O(NlogN)의 시간복잡도를 가집니다.

[2]

1. 어떤 부분이 어려운지?

BFS로 미로의 Key와 시작점 간의 거리를 그래프로 만들어야 한다는 아이디어를 떠올리지 못했습니다.
BFS로 얻은 그래프의 노드들이 번호가 아닌 좌표로 나타나기 때문에 MST를 만드는 구현이 까다로웠습니다.

2. 어떻게 해결하는지?

각 key좌표마다 key_idx를 부여하여 크루스칼 알고리즘을 구현해 해결했습니다.

3. 시간복잡도는?

bfs()가 visited[MX][MX]를 채우는 데에 O(N^2), [1]에 사용했던 크루스칼 알고리즘이 O(NlogN)의 시간복잡도를 가지므로 최종적으로 O(N^2)의 시간복잡도를 가집니다.

[3]

1. 어떤 부분이 어려운지?

강의의 MST와 거의 유사하므로 문제 자체는 어렵지 않았습니다.

2. 어떻게 해결하는지?

크루스칼 알고리즘에서 같은 그룹으로 만들 때 문제의 요구(경계 정도의 증가)에 맞도록 조건을 수정해 해결했습니다.

3. 시간복잡도는?

수정한 부분이 시간복잡도에 큰 영향을 미치지 않으므로 [1]과 마찬가지로 O(NlogN)의 시간복잡도를 가집니다.

[tjdeo1102]

1-1 프림 알고리즘을 활용해 풀었고, 풀이 자체는 어렵지 않았지만, 예외 처리의 부분에서 실수한 부분이 조금 아쉬웠다.
1-2 기본적인 프림 알고리즘에 다음의 조건을 추가해서 구현
-문제의 조건에 의해 그룹이 다른 경우만 사심경로로 인정되기에, 두 노드 사이의 간선을 추가할 때, 같은 그룹들의 간선을 미리 제외
1-3 나올 수 있는 최대 간선은 m개이고 우선 순위 큐에 들어갔다가 나온 간선은 다시 들어갈 수 없다. 우선순위 큐는 이분 탐색에 의한 정렬이 발생한다. 여기서 발생하는 최악의 시간은 O(log(n)) ==> 한 정점에서 나오는 간선의 개수의 최대 n-1
우선순위 큐에 insert의 시점은 어떤 간선이 선택될 때 일어나므로 m*O(log(n))=O(mlog(n))이라고 생각한다.

2-1 BFS방식과 유사한 프림 알고리즘을 활용해 풀었고, 로봇이 복제되는 부분의 조건을 어떤 방식으로 구현해줘야 할지 많이 고민했다.
2-2 기본적인 프림 알고리즘에 다음의 흐름과 조건을 통해 구현
-MST의 과정 속에서 1. 해당 위치가 벽인 경우 2. 해당 위치가 이미 비용이 적은 로봇이 왔던 경우에는 탐색 제외(by 로봇의 복제) 조건 추가
-nxt간선 추가 부분은 2차원 BFS의 방식과 유사하게 해당 위치에서 4방향의 간선만 존재
-해당 위치가 열쇠가 있는 곳인 경우 비용이 0인 로봇이 새롭게 추가 우선순위 큐에 삽입 && cost비용 result에 더함
2-3 각 지점이 전부 노드라고 하면, 각 노드를 잇는 간선을 만들었을 때, (n-1)^2 개가 나오고 여기에 프림 알고리즘을 적용한것과 같은 원리이므로 O(n^2log(n))이라고 생각한다.

3-1 기본 프림 알고리즘에서 비용 + 가중치가 추가된 원리였고, 가중치 부분은 따로 계산해서 출력이 가능했기에 어렵진 않았다.
3-2 기본 프림 알고리즘 적용 출력하기 전 가중치 t에 대한 계산 값을 구한 후, 출력값에 더해줬다.
3-3 기본 프림 알고리즘의 시간복잡도인 O(mlog(n))이라고 생각한다.

[vuswltmd]

int find(int x){
  if(p[x] < 0) return x;
  return p[x] = find(p[x]);
}

bool is_diff_group(int u, int v){
  u = find(u); v = find(v);
  if(u == v) return 0;
//if(p[u] == p[v]) p[u]--;
  if(p[u] < p[v]) p[v] = u;
  else p[u] = v;
  return 1;
}

union find의 틀에서 주석처리된 부분이 왜 존재하는 지 의견을 나누어 보았으나 해결하지 못해 질문드립니다.

[joonas-yoon]

주석처리된 부분을 해제하면 accept인데, 그렇지 않으면 wrong answer이여서 질문주시는 건가요?
어떤 문제를 풀다가 생긴 일인지 문맥도 적어주실 수 있을까요