[알고리즘/그리디] 1080번 : 행렬 - python

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

1080번: 행렬

 

---

• 문제
• 소요시간: 15분(아이디에이션 실패)

---

• 설계하기(접근방법) 

1. 입력받기

행렬을 기존 행렬과 목표 행렬로 나누어 입력받는다

 

2. 구현하기

먼저 3*3의 배열을 뒤집을 수 있는 기능을 구현한다

range(3)의 이중 for문을 구현해서

x = 1 - x의 방식으로 뒤집는다

 

이 문제의 핵심은 한번 지나간 행렬은 다시는 뒤집지 못한다는 것이다

즉 그리디 알고리즘처럼 지금 당장 뒤집으면서 문제를 해결해나가야 한다.

 

3*3의 배열을 뒤집는 것이니 왼쪽 위부터

각각의 배열의 크기에 3을 빼준 만큼 검사를 하며 뒤집는다

 

즉 4 * 4의 배열은

 

0번째, 1번째의 열과  0번째, 1번째의 행을 검사하며 뒤집으면 끝이다

 

현재 배열과 목표 배열의 숫자(0 or 1)이 다른 경우

뒤집는 function을 실행하고 cnt += 1 , 아닌 경우 pass한다

 

 

3. 출력하기

다 뒤집어본 후 목표 리스트와 같다면

뒤집은 횟수를 출력하고

 

같게하지 못했다면 -1을 출력한다

 

 

 

---

• 코드(출력)

def change3_3(list, start_list_num, start_index_num):
    for i in range(3):
        for j in range(3):
            list[start_list_num + i][start_index_num + j] = 1 - list[start_list_num + i][start_index_num + j]


n, m = map(int,input().split())

origin_list = []
changed_list = []

trial = 0
checker = 0

for _ in range(n):
    origin_list.append(list(map(int, input())))

for _ in range(n):
    changed_list.append(list(map(int, input())))

for i in range(n - 2):
    for j in range(m - 2):
        if origin_list[i][j] != changed_list[i][j]:
            change3_3(origin_list, i , j)
            trial += 1

for i in range(n ):
    for j in range(m):
        if origin_list[i][j] != changed_list[i][j]:
            trial = -1

print(trial)

---

• 얻어갈 부분

1. 문제의 아이디어도 떠올리지 못했다. 거시적으로 문제를 풀려고 하니 아이디어가 보이지 않았다. 아이디어가 보이지 않는다면 케이스를 생각하면서 규칙을 찾아보자.

 

이 문제의 경우에는 1번째, 2번째부터 인덱스를 뒤집어본다면 한 번 지나간 인덱스는 다시는 뒤집지 못한다는 것을 발견할 수 있었을 것이다.

 

그 이유는 인덱스를 개별적으로 뒤집지 못하기 때문에, 뒤에서 뒤집었을 때 앞에서 판단한 인덱스에 영향을 미치면 다시 돌아가서 뒤집어야 하는데, 그러면 방금 뒤집은 인덱스에 또 영향을 미치기 때문이다. 모든 구역을 겹치지 않게 3*3으로 나누어 뒤집을 수 있는 것이 아니기 때문에 앞에서부터 검사하는 것이 합리적이다.

 

2. 복잡한 기능이 여러 번 들어간다면 함수를 선언해서 푸는 것이 더 빠를 수도 있다.