이 문제를 보고 든 생각 :
이거를 내가 어떻게 구해 🥴
그리디인가....라는 느낌이 들기는 했지만 어떻게 그리디하게 풀지 생각이 안나서 풀이를 찾아봤다.
역시 그리디였고 풀이는 내가 바꿀수 있는거만 바꾸고 이게 맞으면 다음 칸으로~
내가 바꿀 수 있는 것만 신경쓰고 바꾼 다는게 우리 인생에서 꼭 필요한 생각같다.
내가 바꿀 수 있는 것과 없는것을 구분하는 지혜와 바꿀 수 있는 것에 집중하는 능력이 중요하다.
그냥 알고리즘 풀다가 드는 뻘생각...ㅋㅋㅋ
현재 내 위치만 보고 내 위치의 원소가 같은 위치에서의 B행렬과 일치하지 않는다면 뒤집기 때문에 그리디라고 한다.
근데 왜 이게 최소 횟수지?
순서대로 하는게 최소인가 왔다갔다하면서 최소로 바꿀수도 있는거 아닌가?
아 예를 들어 내부에 있는거 먼저 하고 나서 다른 거 하면 이미 바꾼게 의미가 없겠구나..
내 위치의 칸 값과 goal의 칸 값이 동일하면 이후론 신경쓰지 않아도 되니까 Pass한다고 생각하자..
근데 확실히는 이해가 안된다..왜지..
def flip(i,j) :
for x in range(i,i+3) :
for y in range(j,j+3) :
if original[x][y] == 0 :
original[x][y] = 1
else : original[x][y] = 0
if __name__=="__main__" :
n,m = map(int,input().split())
original =[list(map(int,list(input()))) for _ in range(n)]
goal =[list(map(int,list(input()))) for _ in range(n)]
cnt = 0
for i in range(n-2) :
for j in range(m-2) :
if original[i][j] != goal[i][j] :
flip(i,j)
cnt+=1
print(-1 if original != goal else cnt)
참고 블로그 :
https://hongcoding.tistory.com/75
[백준] 1080 행렬 (Python 파이썬)
문제 설명 https://www.acmicpc.net/problem/1080 0과 1로 이루어진 행렬 A 와 행렬 B가 주어질 때, 행렬 A를 행렬 B로 전환하는데 필요한 횟수를 구하는 문제이다. 이 때, 1회 전환하다는 것은 3x3의 행렬을 뒤
hongcoding.tistory.com
https://velog.io/@dding_ji/baekjoon-1080
백준 1080. 행렬 (Python/파이썬) (그리디 알고리즘)
🔎 백준 1080번 행렬 문제를 풀어보자! (그리디 알고리즘, 파이썬)
velog.io
https://puleugo.tistory.com/39
[백준 1080] 행렬 해설 및 풀이 (파이썬)
백준 알고리즘 1080번 | 행렬 https://www.acmicpc.net/problem/1080 문제 0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작
puleugo.tistory.com
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
| [Python/BOJ] 백준2212 센서_그리디 (0) | 2022.10.08 |
|---|---|
| [Python/BOJ] 백준2138 전구와 스위치_그리디 (1) | 2022.09.30 |
| [Python/BOJ] 백준 2615 오목_구현 (0) | 2022.09.26 |
| [Python/BOJ] 백준 1106 호텔_DP (1) | 2022.09.19 |
| [Python/BOJ] 백준 1713 후보 추천하기_구현 (0) | 2022.09.02 |