BOJ 11975 - Build Gates 링크
(2023.07.20 기준 G3)

문제

좌표 (0, 0)에서 시작하여 주어지는 방향에 따라 1씩 움직이며 울타리를 이어나간다.
이 때, 생기는 모든 울타리 영역과 바깥을 연결하기 위해 설치해야 하는 문의 최소 개수 출력

알고리즘

오일러 지표

풀이

영역이 하나라면 문은 하나만 설치하면 된다.
꼭지점만 맞닿아 있는 두 영역이 생긴다면 문은 각 영역마다 하나씩 설치하면 된다.
만약 면이 맞닿아 있는 두 영역이 생긴다면? 문을 각 영역마다 하나씩 설치해도 되고, 맞닿아 있는 면에 하나와 두 영역 중 한 영역과 바깥과 이어지는 문 하나를 설치해도 된다. 결국은 두 개다.

결국, 문의 최소 개수는 영역의 개수. 즉, 면의 개수이다.

평면에서의 오일러 지표는 v - e + f = 1이다. 그러므로 (0,0)에서부터 시작하여 주어지는 길 따라 움직이며 생기는 점과 선을 모두 중복되지 않게 저장하고,
f(면의 개수) = 1 - v(점의 개수) + e(선의 개수)를 계산하면 된다.

코드

• C++

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

typedef pair<int, int> pii;
typedef pair<pii, pii> ppp;

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

    int N; cin >> N;
    int i = 0, j = 0;

    // 점, 선
    set<pii> v; v.insert({i, j});
    set<ppp> e;

    // 방향
    map<char, int> dir = {{'N', 0}, {'E', 1}, {'S', 2}, {'W', 3}};
    int di[4] = {0, 1, 0, -1};
    int dj[4] = {1, 0, -1, 0};

    // 점과 선을 중복되지 않게끔 해시 맵에 저장
    string path; cin >> path;
    for (char c: path){
        int d = dir[c];
        int ii = i + di[d], jj = j + dj[d];

        v.insert({ii, jj});
        e.insert({min(pair(i, j), pair(ii, jj)), max(pair(i, j), pair(ii, jj))});

        i = ii; j = jj;
    }

    // v - e + f = 1
    cout << 1 - v.size() + e.size();
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
i = j = 0

# 점, 선
v = {}; v[(i, j)] = 1
e = {}

# 방향
dir = {'N': 0, 'E': 1, 'S': 2, 'W': 3}
di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

# 점과 선을 중복되지 않게끔 해시 맵에 저장
for c in input().strip():
    d = dir[c]
    ii = i + di[d]; jj = j + dj[d]

    v[(ii, jj)] = 1
    e[(min((i, j), (ii, jj)), max((i, j), (ii, jj)))] = 1

    i = ii; j = jj

# v - e + f = 1
print(1 - sum(v.values()) + sum(e.values()))