[BOJ 백준] 17609번 1647번 (C++) | 백준 스터디 2주차

백준 스터디 2주차 (2022-03-22 TUE ~ 2022-03-28 MON 📚)

🥈 17609번 - 회문

❔ 문제 바로가기

⭐ 풀이의 핵심

📌 주요 조건

• 회문: 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열 ex) abba, kayak
• 유사회문: 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열 ex) summuus

---

• 출력 값
  • 회문일 경우 0
  • 유사회문일 경우 1
  • 그 외는 2

👉 투 포인터 활용

• 입력 받은 문자열(str)에 대해 첫 번째 인덱스를 가리키는 포인터 하나(i), 마지막 인덱스를 가리키는 포인터 하나(j) 선언
• 한 문자를 삭제하여 유사회문을 만들 수 있는 기회가 있는지 여부를 체크하는 bool 변수(chance) 선언
• i < j 인 동안 탐색 진행
  • str[i] == str[j]일 경우
  • str[i] != str[j]일 경우
    • chance == true인 경우 ✔ 유사회문인지 재귀 호출로 체크
    • chance == false인 경우

🔽 코드 (C++)

#include <iostream>
#include <vector>
using namespace std;

int checkStr(string str, int i, int j, bool chance) {
    while (i < j) {
        if (str[i] == str[j]) {
            i++;
            j--;
            continue;
        }

        // 그 자체로 회문은 아닌 경우 + 한 문자 삭제할 수 있는 기회 있는 경우
        if (chance) {
            // 유사회문인 경우
            if (checkStr(str, i+1, j, false) == 0 || checkStr(str, i, j-1, false) == 0) {
                return 1;
            }
            // 회문도 유사회문도 아닌경우
            return 2;
        }

        // 그 자체로 회문은 아닌 경우 + 한 문자 삭제할 수 있는 기회 없는 경우
        // 회문도 유사회문도 아닌 경우
        return 2;
    }

    // 회문인 경우
    return 0;
}

int main() {
    int T;
    scanf("%d", &T);

    for (int i=0; i<T; i++) {
        char ch[100001];
        scanf("%s", ch);
        string str = ch;
        int endIdx = str.size()-1;
        printf("%d\n", checkStr(str, 0, endIdx, true));
    }

    return 0;
}

🥇 1647번 - 도시 분할 계획

❔ 문제 바로가기

⭐ 풀이의 핵심

📌 주요 조건
i) 유지비의 합을 최소로 만들 것
ii) 마을을 두 개의 분리된 마을로 분할할 것

i) Minimum Spanning Tree 를 구한 후
ii) 해당 MST에서 가장 가중치가 큰 길을 하나 제거하여 두 개의 마을로 분리

• 각각의 house(집)은 node
• road(길)은 edge로
• cost(길의 유지비)를 edge의 가중치로 갖는 그래프
  
  

📌 입력 조건
2 <= 집의 개수 <= 100,000
1 <= 길의 개수 <= 1,000,000

Kruskal vs Prim ❓

• Kruskal O(ElogE), Prim O(N^2)의 복잡도를 가짐
• 주어진 조건에서 E인 길의 개수가 N(N-1)/2 보다 작으므로 Kruskal's Algorithm 활용

🔽 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Road { // edge
    int houseA; // node1
    int houseB; // node2
    int cost; // edge의 가중치
};
vector<int> parents(100001);

bool cmp(const Road &a, const Road &b) {
    return a.cost < b.cost;
}

int getParent(int house) {
    if (parents[house] == house) {
        return house;
    }
    return parents[house] = getParent(parents[house]); // path compression
}

void unionHouses(int houseA, int houseB) {
    int a = getParent(houseA);
    int b = getParent(houseB);
    if (a < b) { parents[b] = a; }
    else { parents[a] = b; }
}

int main() {
    // 집의 개수 N, 길의 개수 M
    int N, M;
    scanf("%d %d", &N, &M);

    // A번 집과 B번 집을 연결하는 길의 유지비가 C
    int A, B, C;
    vector<Road> roads;
    for (int i=0; i<M; i++) {
        scanf("%d %d %d", &A, &B, &C);
        roads.push_back({A, B, C});
    }

    // Kruskal's Algorithm 활용
    // Road(edge)의 가중치를 기준으로 오름차순 정렬
    sort(roads.begin(), roads.end(), cmp);

    // House(node)의 parents 정보 초기화
    // 처음에는 각자 자기 자신이 parents
    for (int i=1; i<=N; i++) {
        parents[i] = i;
    }

    vector<int> selectedRoads;
    for (int i=0; i<M; i++) {
        // parent가 다르다는 것은 아직 두 House 사이에 경로가 없다는 뜻 (사이클 X)
        if (getParent(roads[i].houseA) != getParent(roads[i].houseB)) {
            // parent를 같게 만들어 하나의 그래프로 합치기
            unionHouses(roads[i].houseA, roads[i].houseB);
            // Road의 가중치 저장
            selectedRoads.push_back(roads[i].cost);
        }
    }

    // 마을 분할
    // 선택된 Road의 가중치 중 가장 큰 가중치를 갖는 Road는 제외하고 가중치 합 구하기
    int count = selectedRoads.size() - 1;
    int answer = 0;
    for (int i=0; i<count; i++) {
        answer += selectedRoads[i];
    }

    // 없애고 남은 길 유지비의 합의 최솟값을 출력
    printf("%d", answer);

    return 0;
}