백준 34064 (C++ ) 밤(Time For The Moon Night)

최초 업로드: 2025-08-03 14:09:56

최근 수정 시간: 2025-08-03 14:10:20

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] 밤(Time For The Moon Night)

[문제 링크](https://www.acmicpc.net/problem/34064)

## 문제 설명

떨려오는 별빛 반짝이는데

넌 어디를 보고 있는지

금방이라도 사라질 것 같은데

나는 밤하늘을 달려 너에게 가려고 한다. 밤하늘은 $N\times M$ 크기의 격자로 표현되며, 각 칸은 $(1,1)$부터 $(N,M)$까지의 좌표로 나타낼 수 있다. 나는 밤하늘에서 상하좌우 방향으로 한 칸씩 이동할 수 있다.

이 격자에는 $K$개의 별이 존재하며, 이중 $i$번째 별은 격자의 특정 칸 $(X_i,Y_i)$를 온전히 차지하고 있다. 따라서 별이 있는 칸으로는 이동할 수 없다.

나는 $(a_1,b_1)$과 $(a_2,b_2)$를 각각 왼쪽 아래와 오른쪽 위 꼭짓점으로 하는 축에 평행한 직사각형 안에서, 별이 위치하지 않은 원하는 좌표에서 출발할 수 있다. 마찬가지로, 너는 $(a_3,b_3)$와 $(a_4,b_4)$를 각각 왼쪽 아래와 오른쪽 위 꼭짓점으로 하는 축에 평행한 직사각형 안에서 별이 위치하지 않은 원하는 좌표에서 시작할 수 있다.

내가 상하좌우로 인접한 칸으로 이동해 가며 너를 만나러 갈 수 있는 시작 위치의 조합의 수를 구해야 한다. 시작 위치 조합이 다르다는 것은 나의 시작 위치와 너의 시작 위치 중 하나 이상이 다르다는 것을 의미한다. 두 사람이 같은 위치에서 시작할 수 있다는 점에 유의하라.

## 입력

첫째 줄에 격자의 크기를 나타내는 두 정수 $N,M$과 별의 개수 $K$가 공백으로 구분되어 주어진다.

둘째 줄부터 $K$개의 줄에 걸쳐, 그중 $i$번째 줄에는 $i$번째 별의 위치를 나타내는 $X_i,Y_i$가 공백으로 구분되어 주어진다.

그다음 4개의 줄에 걸쳐, 그중 $i$번째 줄에는 $a_i,b_i$가 공백으로 구분되어 주어진다.

## 출력

상하좌우로 이동해서 두 사람이 만날 수 있는 시작 위치 조합의 수를 출력하라.

## 풀이
#### 시작 정점에서 도착 정점으로 이동 가능한지 여부는 dfs로 찾았고, 총 도착 가능한 개수는 분리집합으로 총 개수를 찾아주었다.

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

int n, m, k;
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};
int parent[250000], cnt[250000];

int _find(int x) {
    if(parent[x]==x) return x;
    return parent[x] = _find(parent[x]);
}

bool _union(int x, int y) {
 x = _find(x);
 y = _find(y);
 if(x==y) return false;
 if(x<y) {
 parent[y] = x;
 cnt[x] += cnt[y];
 } else {
 parent[x] = y;
 cnt[y] += cnt[x];
 }
 return true;
}

int getPos(int x, int y) {
    return x*m+y;
}

void dfs(int x, int y) {
 for(int i=0;i<4;i++) {
 int nx = x+dx[i];
 int ny = y+dy[i];
 if(nx<0 || nx>=n || ny<0 || ny>=m || cnt[getPos(nx, ny)]==-1) continue;
 if(!_union(getPos(x, y), getPos(nx, ny))) continue;
 dfs(nx, ny);
 }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;

for(int i=0;i<n*m;i++) {
 parent[i]=i;
 cnt[i]=1;
 }
 while(k--) {
 int x, y; cin >> x >> y;
 cnt[getPos(x-1, y-1)]=-1;
 }
 int x1, y1, x2, y2, x3, y3, x4, y4;
 cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
 for(int i=0;i<n;i++) {
 for(int j=0;j<m;j++) {
 if(cnt[getPos(i, j)]!=-1 && !(x3-1<=i && i<=x4-1 && y3-1<=j && j<=y4-1)) {
 cnt[getPos(i, j)]=0;
 }
 }
 }

long long total=0;
 for(int i=x1-1;i<x2;i++) {
 for(int j=y1-1;j<y2;j++) {
 if(cnt[getPos(i, j)]!=-1) {
 dfs(i, j);
 total += cnt[_find(getPos(i, j))];
 }
 }
 }
 cout << total;
}
```