[프로그래머스] (C++) 섬 연결하기

문제

• 링크

접근 방식

• 우선 costs를 정렬한다.
• 가장 적은 cost 다리부터 건설 한다.
  • 연결되는 섬은 연결되었다고 기록
• 그 다음 다리를 건설 한다.
  • 다리가 이미 연결된 두 섬을 연결한다면 PASS
  • 한 섬이라도 새로 연결된다면 다리 건설
    
    • 새로 연결되는 섬은 연결되었다고 기록
• 모든 섬이 한번씩이라도 연결됬으면 연결 완료

소스 코드 (1차)

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int> > costs) {
  int answer{0};
  bool* boolList{new bool[n]()};
  sort(costs.begin(), costs.end(), [](const vector<int> & a, const vector<int> & b) {
    return a.at(2) < b.at(2);
  });
  for (auto iter = costs.begin(); iter != costs.end(); iter++) {
    int from = iter->at(0);
    int to = iter->at(1);
    if ((boolList[from] == true) && (boolList[to] == true)) {
      continue;
    } else {
      if (boolList[from] == true) {
        boolList[to] = true;
      } else if (boolList[to] == true) {
        boolList[from] = true;
      } else {
        boolList[from] = true;
        boolList[to] = true;
      }
      answer += iter->at(2);
    }
  }
  return answer;
}

채점 결과 (1차)
정확성: 25.0

합계: 25.0 / 100.0

문제 원인

• 다리가 이미 연결된 두 섬이라도 연결이 필요한 경우가 생김
  • 예를 들면, 섬 A-B-C가 연결되있고 따로 섬 D-E-F가 연결된 경우가 생긴다. (겉으로 봐서는 A, B, C, D, E, F다 어느 다리와 연결되었지만 모든 섬들이 다 하나로 연결된 것이 아니다.)

해결 방법

• 섬마다 사이클을 기록하는 테이블을 두어서 이 사이클이 하나로 통일 되었을 때 연결이 다 되었다고 판단
• 다리로 섬을 연결할 때 이미 연결된 섬의 사이클 숫자를 연결되는 섬의 사이클 숫자로 덮어 씌움

소스 코드 (2차)

 

// [프로그래머스] 섬 연결하기

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int> > costs) {
  int answer{0};
  int* cycleList{new int[n]()};
  for (int i = 0; i < n; i++) {
    cycleList[i] = i;
  }
  sort(costs.begin(), costs.end(), [](const vector<int> & a, const vector<int> & b) {
    return a.at(2) < b.at(2);
  });
  for (auto iter = costs.begin(); iter != costs.end(); iter++) {
    int from = iter->at(0);
    int to = iter->at(1);
    if (cycleList[from] == cycleList[to]) {
      continue;
    } else {
      int temp = cycleList[to];
      for (int i = 0; i < n; i++) {
        if (cycleList[i] == temp) {
          cycleList[i] = cycleList[from];
        }
      }
      answer += iter->at(2);
    }
  }
  return answer;
}

채점 결과 (2차)

정확성: 100.0

합계: 100.0 / 100.0