[BOJ] 1080번 : 행렬

백준 1080번 : 행렬

🔗 문제 링크

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

1080번: 행렬

 

---

💬 문제

 그리디(greedy) 알고리즘 에 대해 충분히 이해한 후 문제를 풀 것을 추천드린다.

전형적인 그리디 문제인 동전 문제와 달리 결코 쉽지 않았다.

 

1. 0과 1로만 이루어진 행렬 A와 B가 주어진다.
   
   - 행렬 A와 B의 크기는 같다
   
   
2. 행렬 A의 원소 일부분을 뒤집어 행렬 B로 만들고, 뒤집는데 필요한 횟수의 최솟값을 구하면 된다.
   
   - 행렬 A에서 3 x 3 크기로만 원소들을 뒤집을 수 있다
   
   - 만약 행렬 A를 B로 바꾸지 못한다면, -1을 출력해준다
   
   

반응형

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 행렬의 크기 N과 M이 주어지고, 2번째 줄부터 N개의 줄에 행렬 A, N+2번째 줄부터 행렬 B가 주어진다.

각각을 줄바꿈으로 잘라준 뒤, 1번째 줄은 N과 M으로 할당해주고, 행렬 A와 행렬 B는 2차원 배열로 만들어준다.

예제 1의 경우, N=3, M=4,

행렬 A = [ [ 0, 0, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 0 ] ],

행렬 B = [ [ 1, 0, 0, 1 ], [ 1, 0, 1, 1 ], [ 1, 0, 0, 1 ] ]로 나눠주면 된다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] JS로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

💻 풀이

이 문제는 그리디 알고리즘으로 풀어볼 수 있다.

🔑 풀이1

• 행과 열인 N과 M, 그리고 행렬 A와 B를 정수화하여 할당해준다.
  
  
• 3 x 3 부분 행렬씩 뒤집어주기에 3 x 3에서 맨 왼쪽 위 원소만 체크해주면 된다.
  
  - 3 x 3 부분 행렬이 전체 행렬 A와 B를 넘어가면 안 되므로, N-2와 M-2 범위 내에서만 체크해준다

• 만약 뒤집어야 할 원소가 있다면 flip 함수로 그 부분 행렬을 뒤집어주고, count를 추가해준다.
  
  - i와 j는 부분 행렬에서 맨 왼쪽 위 원소만 체크해주므로, 부분 행렬 전체를 뒤집기 위해 범위를 3씩 더해준다
  
  - 그리고 0을 1 혹은 1을 0으로 바꿔주는 것이므로, 1에서 그 원소값을 빼준다
  
  
• 뒤집고 난 뒤에 뒤집힌 A와 B를 비교해 서로 동일하면 뒤집은 횟수 count를 출력해주고, 그렇지 않으면 -1을 출력해준다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split("\n");
const [N, M] = input.shift().split(" ").map(Number);
const A = input.slice(0, N).map((item) => item.split('').map(Number));
const B = input.slice(N, N*2).map((item) => item.split('').map(Number));

console.log(solution(N, M, A, B));

function solution(N, M, A, B) {
    let count = 0;
    
    // 뒤집어야 할 원소가 있는지 확인
    for (let i=0; i < N-2; i++) {
        for (let j=0; j < M-2; j++) {
            if (A[i][j] !== B[i][j]) {
                flip(i, j);
                count++;
            }
        }
    }
    // 행렬 A와 B가 동일한지 체크
    for (let i=0; i < N; i++) {
        for (let j=0; j < M; j++) {
            if (A[i][j] !== B[i][j]) {
                count = -1;
            }
        }
    }
    return count;
}

// 요소 뒤집기
function flip (x, y) {
    for (let i=x; i < x+3; i++) {
        for (let j=y; j < y+3; j++) {
            A[i][j] = 1 - A[i][j];
        }
    }
}

 

시간은 다음과 같이 걸렸다.