Baekjoon #11811 데스스타

데스스타

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

11811번: 데스스타

 

문제

젊은 제다이 이반의 임무는 데스스타에 침투하여 파괴하는 일이다. 데스스타를 파괴하기 위해서는 길이 N의 음이 아닌 정수 수열 ai가 필요하다. 그러나 이반은 이 수열을 가지고 있지 않다. 대신 그에게는 오랜 친구 다스 베이더에게 받은 쪽지가 하나 있다. 이 쪽지에는 그 수열이 만족해야 하는 조건이 적혀 있다. 이 쪽지에는 크기 N의 정사각 행렬이 있는데, i번째 행 j번째 열에 적힌 숫자는 ai와 aj에 비트연산 and를 수행한 결과값이다. 하지만 안타깝게도 광선검에 의해 쪽지가 손상되었고 이반은 행렬의 주 대각선에 있는 숫자를 읽을 수 없게 되었다. 원래 배열을 재구성하여 임무를 수행해야 하는 이반을 도와주자. 답은 유일하지 않을 수 있지만, 항상 존재하도록 주어진다.

입력

입력의 첫 번째 줄에는 행렬의 크기 N (1 ≤ N ≤ 1000)이 주어진다. 다음 N개의 줄에는 행렬의 각 원소인 N개의 숫자 mij (1 ≤ mij ≤ 10^9)가 주어진다.

 

출력

정확히 한 줄에 문제의 조건을 만족하는 N개의 음이 아닌 정수를 출력한다. 각 정수는 10^9보다 같거나 작아야 한다. 답이 여러 개인 경우 아무거나 출력한다.

---

비트 연산(and, or) 의미를 알고 손으로 예제를 한번 해보면 쉽게 풀 수 있는 문제이다.

 

AND 연산은 다음과 같다.

A	B	AND (&)
0	0	0
1	0	0
0	1	0
1	1	1

 

OR 연산은 다음과 같다.

A	B	OR (|)
0	0	0
1	0	1
0	1	1
1	1	1

 

---

풀이

먼저, 대각선을 기준으로 대칭이므로 절반만 확인하면 된다.

예를 들어 Aij를 Ai&Aj라고 했을 때 (3*3에서)

0	A12	A13
A21	0	A23
A31	A32	0

 

아래 설명에서는 4bit 기준으로만 설명. (실제로 int값을 사용하면 16bit)

 

AND 연산을 했을 때 그 비트 값이 1이라는 뜻은 피연산자 2개는 모두 해당하는 위치의 비트 값이 1이라는 뜻이다.

예를 들어, 3(0011)과 5(0101)을 AND 연산을 했을 때의 값은 1(0001)이다.

여기서 가장 오른쪽 자리의 결과 값이 1이라는 것은 피연산자(3, 5)모두 가장 오른쪽 자리의 비트 값이 1이라는 뜻이다.

 

따라서 A와 B의 AND 연산 값이 1(0001)일 경우에는 A와 B의 첫번째 비트 값이 1이고, 

AND 연산 값이 3(0011)이면 A와 B의 첫번째, 두번째 비트 값이 1이라는 뜻이다.

 

즉 AND 연산 결과값으로 피연산자들의 값이 1인 비트 값의 위치를 알 수 있다.

 

---

각 수열의 값은 0(0000)으로 시작했을 때 아래의 식이 성립한다.

 

row: i, column: j

Ai = Ai or (Ai&Aj)

Aj = Aj or (Ai&Aj)

 

* 0으로 시작했기 때문에 1의 자리를 확정 지으면 그 자리에 1을 넣으면 된다.

 

(이 방법은 1의 위치를 먼저 추리하고 그 이후에 0으로 채워넣는 방법과 유사하다.)

---

---

전체 코드

/*
* 데스스타
* https://www.acmicpc.net/problem/11811
* */

#include <iostream>

using namespace std;

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

    int N;
    int* a;
    cin >> N;
    a = new int[N];
    fill_n(a, N, 0);

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            int t;
            cin >> t;
            if (i >= j) {
                continue;
            }
            else {
                a[i] = a[i]|t;
                a[j] = a[j]|t;
            }
        }
    }

    for (int i=0; i<N; i++) {
        cout << a[i] << " ";    
    }

    return 0;
}​