AtCoder Beginner Contest 224 A부터 D까지 업솔빙

AtCoder Beginner Contest 224 A부터 D까지 업솔빙

이번 대회에서 D번 문제가 내 잊어버린 BFS감을 다시 찾는데 도움이 된 것 같다. 이전에는 BFS문제가 나왔을 때, 이해하는데만 오랜 시간이 걸렸는데, 이제는 이해할 때 생각보다 적은 시간이 걸려서 좋았다. 그리고 D번 문제가 생각보다 잘 만든 문제라서 공부하면서 기분이 좋았다.

C번 문제같은 경우는 일단 완전탐색을 항상 생각하는 것이 중요할 것 같다. 심지어 정렬까지도.

문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다.

A - Tires (*6)

접기/펼치기

문제 설명
문자열 "er"과 "ist"로 끝나는 문자열 $S$가 주어진다.
만약 $S$가 "er"로 끝나면 "er"을 출력하고 그렇지 않으면 "ist"를 출력하라.

문제 해설
문제 나온대로 해결하자. 맨 뒤 문자 r, t만 찾아도 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s; cin >> s;
    cout << (s[s.size() - 1] == 't' ? "ist" : "er");
    return 0;
}

B - Mongeness (*81)

접기/펼치기

문제 설명
$H$개 행과 $W$개 열의 격자로 이루어진 판이 주어진다. 각 판에 있는 격자는 정수가 있고, 맨 위에서 부터 $i$번째, 맨 왼쪽에서 $j$번째 칸에 위치한 숫자는 $A_{i, j}$이다.

다음 조건을 만족하는지 판단하라.

$1 \le i_1 < i_2 \le H, 1 \le j_1 < j_2 \le W$를 만족하는 모든 정수 $(i_1, i_2, j_1, j_2)$에 대해서 $A_{i_1, j_1} + A_{i_2, j_2} \le A_{i_2, j_1} + A_{i_1, j_2}$을 만족하는가?

문제 해설
4중 for문 사용해서 위 조건이 맞나 판단하자.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int h, w; cin >> h >> w;
    int a[h][w];
    for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) cin >> a[i][j];
    bool flag = true;
    for(int i = 0; i < h; i++){
        for(int j = i + 1; j < h; j++){
            for(int k = 0; k < w; k++){
                for(int l = k + 1; l < w; l++){
                    if(a[i][k] + a[j][l] > a[j][k] + a[i][l]) flag = false;
                }
            }
        }
    }
    cout << (flag ? "Yes" : "No");
    return 0;
}

C - Triangle? (*301)

접기/펼치기

문제 설명
$x-y$평면에서 $1$ 부터 $N$까지 번호가 부여된 $N$개의 점이 있다.
점 $i$는 좌표 $(X_i, Y_i)$에 있고, 아무 두 점을 잡아도 항상 서로 다르다.
이 $N$개의 점중 3개의 점을 잡았을 때, 해당 점으로 삼각형을 만들 수 있는 경우의 수를 구하시오.

문제 해설
이 문제는 실전에서 풀 때 그렇게 오래 걸리면 안되는 문제이다. 정형화된 알고리즘이 있기 때문에 다음에는 이런 비슷한 유형의 문제가 나오면 빨리 풀어보자.

좌표를 vector에 담고 정렬을 한 다음 모든 점을 탐색하면서 각 두점의 기울기가 서로 같으면 그 점은 삼각형을 만들 수 없기 때문에 제외하고 개수를 세면 된다. 이때 숫자를 나누면 오차가 생길 수도 있기 때문에 기울기 판병을 할때는 식을 약간 변형해서 곱셈만 있는 식으로 판별하자. 결국은 완전탐색 문제, 3중 for문을 사용하면 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            for(int k = j + 1; k < n; k++){
                if((v[i].first - v[j].first) * (v[j].second - v[k].second) != 
                (v[i].second - v[j].second) * (v[j].first - v[k].first)) ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

D - 8 Puzzle on Graph (*1376)

접기/펼치기

문제 설명
바닥에서 퍼즐을 발견했다.
이 퍼즐은 $9$개 정점과 $M$개 간선으로 이루진 무방향 그래프로 이루어져 있다. 그리고 $8$개 조각이 있다.

$9$개 정점은 순차적으로 $1, 2, ..., 9$번이고, 각 $i = 1, 2, ..., M$에 대해서 $i$번째 간선은 정점 $u_i$와 $v_i$를 연결한다.
8개 조각은 순차적으로 $1, 2, ..., 8$번이고, 각 $j = 1, 2, ..., 8$에 대해서 $j$번째 조각은 정점 $p_j$에 있다.
즉 따라서 1개의 정점에는 조각이 존재하지 않는다.

현진이는 다음 연산을 몇번이고 수행할 수 있다.

비어있는 정점과 인접한 정점에 있는 조각을 선택해서 빈 정점에 해당 조각을 옮긴다.

이 연산을 반복하고 나서 현진의 목표는 이 퍼즐을 완료하는 것이다. 퍼즐은 다음 조건을 만족하면 풀린다.

• 각 $j = 1, 2, ..., 8$에 대해서 조각 $j$가 정점 $j$에 있다.

현진이가 다음 퍼즐을 완료할 수 있는지 판단하라 만약 가능하다면 필요한 최소 연산의 개수를 구하라.

문제 해설
문제를 처음 봤을 때는 어떻게 하는지 몰라서 결국 업솔빙 했는데, 자세히 보니까 최소 연산의 개수를 구하는 것과 인접한 정점에 있는 조각을 바꾸는 연산을 하는 것을 보고 BFS를 사용해야 한다는 것을 깨달아야 했다. 가능한 모든 경우의 수를 찾고, 완료할 수 있는 지점에 있는 값을 출력하면 된다.

일단 이 퍼즐을 BFS로 풀기 위해서는 퍼즐의 상태를 표현하는 방법을 찾아야 하고, 이것을 찾는 것이 이 문제의 핵심이다. 여기서는 퍼즐의 상태를 문자열로 표현했다. 문자열 "123456789"이면 1번 정점에 1번 조각이, 2번 정점에 2번 조각이 있다는 뜻이다. 마지막인 9는 9번 조각이 없기 때문에 결국은 비어있는 정점이고 우리는 이 조각이 있는 위치에 인접한 조각을 움직일 수 있다는 뜻이다.

즉 매 반복마다 9의 위치를 찾고, 9에 인접한 정점과 9에 있는 값을 교체한 상태를 큐에 넣는다. 이때 BFS에서 가장 중요한 점은 방문 여부를 표시하는 것인데 여기서는 map을 사용해서 해결했다. 만약 map에 해당 상태가 이미 존재하다면 이 상태를 만들기 위해서 필요한 최소 연산이 이미 있기 때문에 넘긴다. 해당 상태가 없다면 상태를 map에 넣고, 값은 이전 상태 + 1로 해서 계속 이어나간다.

마지막으로 bfs가 끝나면 우리가 원하는 상태인 "123456789"의 값을 출력하면 되고, 저 상태가 없다면 만들 수 없다는 뜻이기 -1을 출력하면 된다. 다시 강조하지만 bfs에서는 방문 여부를 반드시 표시해서 중복 방문이 없도록 해야한다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int m; cin >> m;
    vector<int> g[9];
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }

    string s = "888888888";
    for(int i = 0; i < 8; i++){
        int num; cin >> num;
        s[num - 1] = (i + '0');
    }

    map<string, int> mp;
    queue<string> q;
    mp[s] = 0;
    q.push(s);
    while(q.size()){
        string top = q.front(); q.pop();
        int idx = 0;
        for(int i = 0; i < 9; i++) if(top[i] == '8') idx = i;

        for(auto x : g[idx]){
            string tmp = top;
            swap(tmp[x], tmp[idx]);
            if(mp.count(tmp)) continue;
            mp[tmp] = mp[top] + 1;
            q.push(tmp);
        }
    }
    cout << (mp.count("012345678") ? mp["012345678"] : -1);
    return 0;
}