[BOJ] 5845번: Perimeter

https://www.acmicpc.net/problem/5845

문제: 밀집이 이어지게 주어지는데 그것의 둘레의 길이를 구하라. 안에 구멍이 생기는 것은 무시한다.

해결: dfs를 가지고 해결할 수 있는데 둘레의 길이를 구해야 하므로 오른손 법칙을 프로그램에 적용시킨다고 생각하면 된다. 그래서 밀집의 좌표에서 시작하는 게 아니라 옆에서부터 벽을 짚고 간다는 느낌으로 생각해야 한다.

그리고 핵심은 바로 set이다. 왜냐면 좌표가 10^6까지 주어지는데 10^12짜리 배열은 선언 자체를 할 수 없기 때문에 set이라는 유용한 도구를 사용해서 좌표를 가지고 놀 수 있게 된다.

내가 허튼짓을 했던 것은 구멍인지 확인하는 함수를 구현하는데 대각선 포함 8방향을 다 봐야 하는데 상하좌우만 보게 해서 문제를 계속 틀렸었다... ㅠ

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;

typedef pair<int, int> Point;
set<Point> object, visited;
int perimeter;

bool isolated(int x, int y)
{
    for (int i = -1; i <= 1; i++)
        for (int j = -1; j <= 1; j++)
            if (object.count(Point(x + i, y + j)))
                return false;
    return true;
}

void visit(int x, int y)
{
    if (object.count(Point(x, y)))
    {
        perimeter++;
        return;
    }
    if (visited.count(Point(x, y)))
        return;
    visited.insert(Point(x, y));
    if (isolated(x, y))
        return;
    visit(x - 1, y);
    visit(x + 1, y);
    visit(x, y - 1);
    visit(x, y + 1);
}

int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    int N, x, y;

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> x >> y;
        object.insert(Point(x, y));
    }

    Point start = *object.begin();
    x = start.first - 1;
    y = start.second;

    visit(x, y);

    cout << perimeter << "\n";
    return 0;
}