BOJ 20118 : 호반우가 길을 건너간 이유

• 문제 링크 : boj.kr/20118
• 난이도 : G2
• 태그 : 애드혹, 해 구성하기

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<pii> ans;
    for(int i = 0; i < min(n,m); i++) {
        ans.emplace_back(i,i);
    }
    if(n < m) {
        for(int i = n; i < m; i++) {
            ans.emplace_back(n-1, i);
        }
    }
    else if(n > m) {
        for(int i = m; i < n; i++) {
            ans.emplace_back(i, m-1);
        }
    }
    if(ans.size() % 2) {
        ans.emplace_back(min(n,m)-2, min(n,m)-1);
    }
    sort(all(ans));

    cout << ans.size() * 2 << "\n";
    for(int i = 0; i < ans.size(); i += 2) {
        cout << ans[i].first << " " << ans[i].second << "\n";
        cout << ans[i+1].first << " " << ans[i+1].second << "\n";
        cout << ans[i].first << " " << ans[i].second << "\n";
        cout << ans[i+1].first << " " << ans[i+1].second << "\n";
    }

    return 0;
}

---

풀이

$A \oplus A=0$을 이용하는 문제이다.

A->B->A->B의 경로를 통해 XOR을 0으로 유지하면서 A에서 B로 나아갈 수 있다.

따라서 경로의 길이가 짝수라면 XOR을 0으로 유지한 채 끝점에 도달할 수 있다.

시작점에서 끝점까지 도달하는 길이가 짝수인 임의의 경로를 찾는다면 문제를 해결할 수 있다.