AtCoder Beginner Contest 213 A부터 E까지 업솔빙

AtCoder Beginner Contest 213 A부터 E까지 업솔빙

D번까지 다 푼 대회이다 22. 이제 브라운 컬러인 400~800 난이도는 Atcoder에서 좀 많이 푸는 실력을 갖춘것 같다. 알고리즘을 몰라도 깡 구현으로 푼 C번 문제같은 경우도 있고, D번문제는 DFS간단한 변형이고, E번 문제도 0-1 BFS인데 격자점에서 다익스트라구현하는 것을 까먹어서 못풀었다. 이런 문제 셋만 계속 나온다면 나도 희망이 있을 것 같다!! 이제 Atcoder에서 살아남으려면 간단한 dp만 공부하면 된다...
이번 대회에서 배운 것은

1. 좌표 압축 알고리즘 기본과 조건
2. 0-1 BFS와 2차원 배열에서 다익스트라 구현

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

A - Bitwise Exclusive Or (*33)

접기/펼치기

문제 설명
$0$과 $255$ 사이에 있는 두 정수 $A$와 $B$가 주어진다. $A xor C = B$를 만족하는 음이 아닌 정수 $C$를 구하라.

문제 해설
XOR의 성질인

• $A xor 0 = A$
• $A xor A = 0$
  을 사용하는 기본 문제이다.

$C = A xor B$라고 하면 주어진 식은 $A xor (A xor B)$ 가 되고, xor끼리는 결합법칙이 성립하므로 $(A xor A) xor B$이다. 따라서 첫번째 성질에 의해 $0 xor B = B$이다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    unsigned int a, b; cin >> a >> b;
    cout << (a ^ b);
    return 0;
}

B - Booby Prize (*26)

접기/펼치기

문제 설명
$1, ..., N$이라고 번호가 부여된 사람 $N$명이 게임을 하고 있다. $i$번째 사람은 $A_i$만큼 점수를 얻었고, 가장 작은 점수를 가진 사람의 등수가 가장 높다.

두번째로 낮은 등수를 가진 사람이 booby 상을 받게 된다. 이 상을 받는 사람은 누구일까? 상을 받는 사람을 나타내는 숫자를 출력해라.

문제 해설
pair을 사용한 정렬을 내림차순으로 하면 맨 앞에 있는 항이 가장 높은 수를 가지고 있으니 가장 낮은 등수인 사람이고, 두번째로 낮은 등수를 가진 사람은 그 배열의 1 인덱스이다.

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
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;
    for(int i = 1; i <= n; i++){
        int num; cin >> num;
        v.push_back({num, i});
    }
    sort(v.begin(), v.end(), greater<>());
    cout << v[1].second;
    return 0;
}

C - Reorder Cards (*481)

접기/펼치기

문제 설명
$H \times W$개 카드가 행렬에 $H$개 행과 $W$개의 열로 배열되어 있다.
각 $i = 1, ..., N$에 대해서 위에서 $A_i$번째 행과, 왼쪽에서 $B_i$번째 열은 $i$라고 적혀있다. 다른 $HW - N$개의 카드는 아무것도 적혀있지 않다.

우리가 할 수 있는 한 많이 다음 두 종류의 연산을 카드에 반복할 수 있다.

• 숫자가 적혀져 있지 않은 행이 있다면 그 행에 있는 모든 카드를 지우고, 남아있는 카드를 위로 올려서 사이를 채운다.
• 숫자가 적혀져 있지 않은 열이 있다면 그 열에 있는 모든 카드를 지우고, 남아있는 카드를 왼쪽으로 옮겨서 사이를 채운다.

위에 있는 과정을 끝나고 난 다음에 남아있는 숫자가 적혀있는 카드의 최종 위치를 구하라.

문제 해설
이 문제를 보자마자 사실은 좌표 압축이라는 알고리즘이 떠올라야 하지만 이 방법은 예전에 한번만 스치듯이 봤기 때문에 떠오르지 않았고, 각 X축과 Y축을 각각 MAP으로 해서 좌표를 기억하는 쌩 구현으로 풀면 되겠다는 생각을 했다. 그래서 처음에 문제를 풀었을 때는 X축과 Y축을 각각 INDEX까지 기억한 pair 배열로 선언해서 정렬을 하고, 맨 처음에 나온 숫자부터 1을 부여하고, map에 저장한다. 그리고 그 map에 이미 숫자가 존재하면 pass하는 방식으로 문제를 풀었다.

그런데 내가 하는 이 알고리즘이 이미 더 세련된 방식으로 누가 이름까지 붙여져 있는 삳태로 존재하고 있었는데, 그것이 바로 좌표 압축(cordinate compression)이다.

좌표 압축은 좌표 사이의 빈 공간이 너무 많아 한 index 배열에 전부 담을 수 없는데, 전체 나오는 숫자 개수는 상당히 적을 때 유용하다. 이 문제에서도 숫자의 범위는 $10^9$이지만 전체 숫자 개수는 $10^5$ 이기 때문에 문제에서 대놓고 좌표압축 기법을 사용하라고 냈다고 할 수 있다. 좌표 압축은 좌표 사이의 빈 공간을 매우는 역할을 하기 때문에 문제에서 요구하는 빈 공간을 채우는데 딱 들어맞는다. 따라서 이 알고리즘을 사용해서 x축과 y축 각각의 좌표에 대한 좌표 압축한 index를 구하면 답이 된다.
좌표 압축 알고리즘은 매우 정형화되어있기 때문에 한번만 공부하면 쉽게 사용할 수 있을 것이다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int h, w, n; cin >> h >> w >> n;
    int a[n], b[n];
    vector<int> x, y;
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
        x.push_back(a[i]);
        y.push_back(b[i]);
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    y.erase(unique(y.begin(), y.end()), y.end());

    for(int i = 0; i < n; i++){
        int dx = lower_bound(x.begin(), x.end(), a[i]) - x.begin();
        int dy = lower_bound(y.begin(), y.end(), b[i]) - y.begin();
        cout << dx + 1 << " " << dy + 1 << "\n";
    }
    return 0;
}

D - Takahashi Tour (*710)

접기/펼치기

문제 설명
Atcoder 공화국에서는 $1$ 부터 $N$까지 번호가 부여되어 있는 $N$개 도시가 있고, $1$부터 $N - 1$까지 번호가 붙여져 있는 도로 $N - 1$개가 있다. 도로 $i$는 도시 $A_i$와 도시 $B_i$를 양방향으로 연결해있고, 이 도로를 사용해서 모든 도시를 방문할 수 있다.

지수는 도시 $1$에서 출발하고, 다음과 같이 여행을 떠날 것이다.

• 만약 지수가 있는 도시에서 방문하지 않은 도시가 연결되어 있다면 이 도시들 중 가장 작은 숫자가 적혀있는 도시로 이동한다.
• 그렇지 않으면
  • 만약 지수가 도시 $1$에 있다면 여행을 종료한다.
  • 그렇지 않으면, 현재 있던 도시 바로 이전에 도착한 도시로 다시 이동한다.

지수가 방문한 순서대로 도시의 수열을 출력하라.

문제 해설
그냥 DFS문제, 변형이라고 하기에도 사실은 부끄럽다. DFS에 그냥 출력문 몇개만 작성하면 끝이기 때문이다. DFS구현하는 법 모르면 그냥 알고리즘을 공부해야한다. DFS, BFS모르면 그래프 문제 못푼다.

이 문제에서 일단 연결된 도시 순서는 무작위로 주어지므로 이것을 작은 숫자 순서대로 이동하려면 정렬을 해야하는데, 일일이 정렬하기 귀찮기 때문에 그냥 자동 정렬이 되어있는 자료구조 set을 이용하자. 그리고 다른 도시로 이동할때 그 도시를 출력하고, 원래 있던 도시에서 나올때 또한 그 도시를 출력하면 답이다.

정답 코드

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

vector<set<int>> g;
vector<int> visit;

void dfs(int node){
    visit[node] = 1;
    cout << node << " ";
    for(auto x : g[node]){
        if(!visit[x]){
            dfs(x);
            cout << node << " ";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    visit = vector<int>(n + 1);
    g = vector<set<int>>(n + 1);
    for(int i = 0; i < n; i++){
        int a, b; cin >> a >> b;
        g[a].insert(b);
        g[b].insert(a);
    }
    dfs(1);
    return 0;
}

E - Stronger Takahashi (*1423)

접기/펼치기

문제 설명
$H$개 행과 $W$개 열의 격자로 이루어진 마을이 있다. 위에서 $i$번째 행과 왼쪽에서 $j$번째 열에 있는 칸이 통과할 수 있다면 "."으로, 벽으로 막혀있다면 "#"으로 나타낸다.

지수는 집에서 수산시장으로 가고 싶다. 지수의 집은 왼쪽에서 맨 위에 있는 칸에 위치해있고, 수산시장은 오른쪽에서 맨 아래에 있는 칸에 위치해있다.

지수는 한번에 위로 한칸, 아래로 한칸, 왼쪽으로 한칸, 오른쪽으로 한칸 이동할 수 있고 마을 밖을 벗어날 수는 없다. 지수는 벽돌을 통과할 수 없지만 지수의 초월적인 힘은 $2 \times 2$ 크기의 칸에 있는 모든 벽돌을 펀치 한번에 부실 수 있고 이 모든 칸은 통과할 수 있다.

지수가 수산시장으로 가기 위해서 필요한 최소 펀치 횟수를 구하라.

문제 해설
이 문제를 BFS로 풀어야 한다는 것은 문제를 보자마자 알 수 있었는데, 격자로된 BFS는 안푼지 너무 오래되서 까먹었었다. 심지어 0-1 BFS라는 알고리즘도 어떻게 구현해야하는지 알고 있었는데, 이렇게 나오는 문제도 처음봤다.

0-1 BFS는 다익스트라 알고리즘을 더욱 빠르게 사용하는 알고리즘으로, 가중치가 0과 1로만 이루어진 그래프에서 사용가능하다. 이 알고리즘은 queue를 사용하는 BFS와 priority_queue를 사용하는 다익스트라와 다르게, deque를 사용한다. 가중치가 0인 노드는 맨 앞에, 가중치가 1인 노드는 맨 뒤에 삽입하고 항상 맨 앞에 있는 노드를 본다면 이 자료구조는 항상 정렬되어 있는 상태라는 점을 이용한다. 왜냐하면 다익스트라는 항상 가장 작은 가중치를 가진 노드를 확인해야 하기 때문이다.

이렇게 하면 그냥 다익스트라를 사용하면 벽이 있는 구역은 가중치를 +1해서 현재 있는 위치의 가중치를 비교해서 현재 있는 가중치보다 값이 크면 최단경로가 아직 없다는 뜻이므로 현재 있는 위치로 초기화해주고, 그렇지 않으면 이미 최단경로가 존재하기 때문에 무시하면 될텐데, 이 문제에서는 one 펀치라는 변형이 주어졌다.

현재 있는 위치에서 one펀치를 날리면
.***.
*****
**T**
*****
.***.

*되어있는 곳 모두를 부실 수 있기 때문에 이 위치 모두를 조사할 때는 가중치 1을 더한 상태에서 조사하고 이 위치에서 dist배열 값이 변경되었다면 deque의 맨뒤에 좌표를 삽입해서 자료구조의 정렬상태를 유지하는 식으로하고 그냥 상하좌우 위치를 확인할 때면 punch를 날리지 않은 상태기 때문에 현재 위치의 가중치 그대로 dist를 비교하면 된다.

일일이 punch를 친 좌표를 구하는게 귀찮지만 이것을 제외하면 전형적인 문제인것 같으니 눈과 머리에 꼭꼭 담아두자.

그리고 memset(0x3f)는 배열이 integer자료형일 때, INF값을 구현하려고 작성한 코드이고 만약에 배열 자료형이 longlong 이라면 memset(0x7f)라고 하면 된다.

정답 코드

#include <iostream>
#include <cstring>
#include <deque>

using namespace std;

int x[] = {1, 0, -1, 0, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2};
int y[] = {0, 1, 0, -1, -1, 0, 1, -1, -1, 1, 2, -2, 2, -2, -1, 1, 2, -1, 0, 1};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int h, w; cin >> h >> w;
    char b[h][w];
    int dist[h][w];
    memset(dist, 0x3f, sizeof(dist));
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            cin >> b[i][j];

    deque<pair<int, int>> dq;
    dq.push_back({0, 0});
    dist[0][0] = 0;
    while(dq.size()){
        int cx = dq.front().first, cy = dq.front().second;
        dq.pop_front();
        for(int i = 0; i < 4; i++){
            int nx = cx + x[i], ny = cy + y[i];
            if(nx < 0 || nx >= h || ny < 0 || ny >= w || b[nx][ny] == '#') continue;
            if(dist[cx][cy] < dist[nx][ny]){
                dist[nx][ny] = dist[cx][cy];
                dq.push_front({nx, ny});
            }
        }
        for(int i = 0; i < 20; i++){
            int nx = cx + x[i], ny = cy + y[i];
            if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            if(dist[cx][cy] + 1 < dist[nx][ny]){
                dist[nx][ny] = dist[cx][cy] + 1;
                dq.push_back({nx, ny});
            }
        }
    }
    cout << dist[h - 1][w - 1];
    return 0;
}