[백준 node.js] 1080번_행렬

백준 그리디 알고리즘 1080번_행렬

난이도 : 실버II

 

문제 설명

입출력

 

문제 풀이 : 행렬 A, B가 주어졌을때 A를 B로 바꾸는 최소 횟수를 구하면 된다. 행렬 변환시는 3*3만 가능하다는것이 중요한 포인트이다.

   A  B  C  D 

E  0  0  0  0

F  0  0  1  0

G 0  0  0  0    A~G는 행열을 구분하기 편하게 임의로 지정한것이므로 무시해도 좋습니다.

입출력으로 주어진 예제는 3*4 행렬이다. 하지만 행렬 변환은 3*3이다. 

3*3변환을 이용하여 3*4를 행할려면 2번을 수행해야한다.  한번 수행할때 A,E 지점부터 C,G지점까지 가능하다.

그러면 G지점이 아직 수행되지않았다. 그 다음엔 B,E지점부터 D,G지점까지(3*3)을 행하면 두번의 연산이 가능하다.

 

하지만 문제에서 최소 횟수를 구해야하므로 연산을 행하기전 시작지점을 A행렬과 B행렬과 비교해서 틀리면 연산을 해주고 횟수를 카운트 해주면된다.

위의 입력을 예지로 연산을 한다면 다음과 같다.

첫번째 (0,0)지점을 A행렬과 B행렬을 비교한다. 똑같으면 연산제외 다음 비교값으로간다. 위의 예제에서는 틀리기 때문에 연산을 수행하고 카운트를 해준다. 한번의 연산을 하게되면 A행렬은 다음과 같아진다.

1 1 1 0

1 1 0 0

1 1 1 0

이후 (0,1)지점을 A행렬과 B행렬을 비교한다. 똑같으면 연산제외 다음 비교값으로간다. 위의 예제에서는 틀리기 때문에 연산을 수행하고 카운트를 해준다. 한번의 연산을 하게되면 A행렬은 다음과 같아진다.

1 0 0 1

1 0 1 1

1 0 0 1

이렇게 되면 B행렬과 일치하게 된다. 총 두번의 연산 과정이 이루어진다.

 

//실버2 행렬
function solution(n, m, list, list2) {
    let count = 0;

    //3*3형태로 검증이므로 해당 테이블 크기에 맞게 계산하기 위해 
    //i, j에 -2를한다.
    for(let i=0; i<n-2; i++){
        for(let j=0; j<m-2; j++){
            if(list[i][j] !== list2[i][j]){
                //3*3테이블의 제일 왼쪽 위에 값만 비교해서 틀리면 3*3테이블의 값을 전체 바꿈
                flip(i, j);
                count += 1;
            }
        }
    }

    for(let i=0; i<n; i++){
        for(let j=0; j<m; j++){
            if(list[i][j] !== list2[i][j]){
                count = -1;
                break;
            }
        }
    }
    
    console.log(count);
}

//테이블 값 변환
function flip(x, y){
    for(let i=x; i<x+3; i++){
        for(let j=y; j<y+3; j++){
            list[i][j] = 1 - list[i][j];
        }
    }
}

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let input = [];
let list = [];
let list2 = [];

rl.on("line", function (line) {
 
   input.push(line)

}).on("close", function () {

    let tmp = input[0].split(' ').map((el)=> parseInt(el));
    let n = tmp[0];
    let m = tmp[1];
    
    //A배열
    let arr = input.slice(1,n+1);
    //B배열
    let arr2 = input.slice(n+1);


    //A,B 배열을 이중배열로 만들고 int형으로 변환
    for(let i=0; i<arr.length; i++){
        list.push(arr[i].split('').map((el)=> parseInt(el)));
        list2.push(arr2[i].split('').map((el)=> parseInt(el)));
    }
  
    solution(n, m, list, list2);

    process.exit();
});

 

* 문제를 제대로 이해하지못해서 다른 블로그를 참고하고 직접 그려보면서 문제를 해결했다. 다소 까다롭고 난이도 있는 문제로 느껴졌다.