백준 25201번 [보드 뒤집기 게임](C++) -yes6686- 티스토리

 

백준 문제 풀이: 25201 [보드 뒤집기 게임]

---

문제 링크: https://www.acmicpc.net/problem/25201

문제 설명:

주어진 격자판의 상태를 특정 규칙에 따라 변경할 수 있는지 판단하는 문제입니다. 격자판의 각 행과 열의 상태를 관리하여 규칙에 맞는지 확인합니다.

입력 조건:

• 첫 번째 줄에 두 정수 n과 m이 주어집니다. (1 ≤ n, m ≤ 100,000)
• 다음 n + m개의 줄에는 좌표 (x, y)가 주어집니다. (1 ≤ x, y ≤ 100,000)
• (x, y)는 빨간색 칸의 위치를 나타냅니다.

출력 조건:

• 모든 행과 열의 빨간색 칸 개수가 짝수라면 "YES"를 출력합니다.
• 그렇지 않다면 "NO"를 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int rowCnt[100001];
int colCnt[100001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    int x, y;

    // n + m개의 좌표를 입력받아 각 행과 열의 빨간색 칸 개수를 관리
    for (int i = 0; i < n + m; i++) {
        cin >> x >> y;
        rowCnt[x]++;
        colCnt[y]++;
    }

    // 각 행과 열의 빨간색 칸 개수가 짝수인지 확인
    for (int i = 0; i < 100001; i++) {
        if (rowCnt[i] % 2 == 1 || colCnt[i] % 2 == 1) {
            cout << "NO" << '\n';
            return 0;
        }
    }

    cout << "YES" << '\n'; // 모든 행과 열의 개수가 짝수인 경우
    return 0;
}
    

---

코드 설명

위 코드는 주어진 좌표를 입력받아 각 행과 열의 빨간색 칸 개수를 확인하여 규칙을 만족하는지 판단합니다.

• 뒤집기 마법의 특징:
  • 뒤집기 마법을 사용하면 선택된 좌표를 기준으로 2×2 칸의 색상이 모두 반전됩니다.
  • 결국 각 행과 열의 빨간색 개수는 항상 짝수 개만큼 변합니다.
• 검사 원리:
  • 처음 격자판 상태에서 각 행과 열의 빨간색 칸 개수를 저장합니다.
  • 입력된 좌표를 기준으로 현재 상태와 원하는 상태를 비교하여 홀/짝성을 확인합니다.
  • 홀수인 경우는 뒤집기 마법으로 만들 수 없는 상태이므로 "NO"를 출력합니다.
  • 모든 행과 열의 칸 개수가 짝수인 경우에만 "YES"를 출력합니다.
• 구현 세부사항:
  • 각 좌표 입력에 대해 `rowCnt[x]`와 `colCnt[y]` 값을 증가시켜 행과 열의 빨간색 개수를 누적합니다.
  • 모든 행과 열을 검사하여 짝수 여부를 확인합니다.

시간 복잡도 분석:

• 입력 처리: O(n + m).
• 행과 열 확인: O(max(n, m)).
• 전체 시간 복잡도: O(n + m).

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
3 2
1 2
2 2
3 2
1 2
3 2

출력:
NO
    

모든 행과 열의 빨간색 칸 개수가 짝수이므로 "YES"를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!