백준 34146 (C++) 잃어버린 섬

최초 업로드: 2025-08-21 19:33:46

최근 수정 시간: 2025-08-21 19:34:11

게시자: rlatjwls3333

카테고리: 백준

# [Silver V] 잃어버린 섬

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

## 문제 설명

빛은 점점 흔들리기 시작했다. 그 흐름은 언제 끊어져도 이상하지 않을 만큼 위태로웠고, 섬을 이루는 원소들도 흩어지기 시작했다.

사람들은 마지막 시도로, 모든 것을 원래의 자리로 되돌리고자 했다. 그들은 어긋난 무늬를 다시 맞추어 섬을 하나로 엮고, 흐트러진 균형을 되찾으려 했다.

섬을 지키기 위한 최후의 노력을 지켜보고, 그들을 위한 해답을 찾아라.

<hr>
섬의 사람들은 모두 한 자리에 모였다. 그들이 있는 땅은 $N\times M$ 크기의 격자로 표현된다. 이때 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 칸을 $(r,c)$로 표기한다.

격자의 각 칸에는 그들이 지켜보고 이루어 온 모든 것들을 상징하는 무늬가 새겨져 있다. 무늬들은 기존의 질서를 잃어버린 채로, 임의의 순서로 배열되어 있다.

섬의 사람들은 격자의 무늬가 좌우대칭이 된다면 질서가 복원될 것이라고 생각하였다.

아래와 같은 예시를 살펴보자. 편의상 각 무늬를 번호로 표기한다. 아래 그림의 왼쪽과 같은 경우, 격자의 무늬들이 좌우대칭이 아니다. 그러나, 무늬들을 적당히 재배열할 경우, 오른쪽과 같이 좌우대칭이 되도록 만들 수 있다.

섬의 사람들은 격자의 무늬를 재배열하고 섬의 질서를 마지막으로 지킬 수 있는지 알고자 한다.

## 입력

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

다음 $N$개의 줄에 걸쳐, 격자의 초기 상태가 주어진다. 각 줄에는 $M$개의 수 $A_{i1},A_{i2},\cdots ,A_{iM}$이 주어지며, $A_{rc}$는 칸 $(r,c)$에 있는 무늬에 대응되는 정수이다.

## 출력

만약 무늬를 재배열하여 격자를 좌우대칭으로 만들 수 있다면, <code>YES</code>를 출력한다.

만약 무늬를 재배열하여 격자를 좌우대칭으로 만드는 것이 불가능하다면, <code>NO</code>를 출력한다.

## 풀이
#### 만약 M이 홀수인 경우 홀수 개인 수가 최대 N개여야 하고, 짝수라면 홀수 개인 수가 없어야 한다.

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

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m; cin >> n >> m;
 map<int, int> nums;
 for(int i=0;i<n;i++) {
 for(int j=0;j<m;j++) {
 int num; cin >> num;
 nums[num]++;
 }
 }

int cnt=0;
 for(auto e : nums) {
 if(e.second%2) {
 if(m%2==0 || ++cnt>n) {
 cout << "NO";
 return 0;
 }
 }
 }
 cout << "YES";
}
```