[Swift] 백준 1080 - 행렬

문제

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

1080번: 행렬

 

코드

let input = readLine()!.split(separator:" ").map { String($0) }.map{ Int($0)!}
let N = input[0]
let M = input[1]

var A:[[Int]] = []
var B:[[Int]] = []
var cnt = 0

for _ in 0...N-1 {
    A.append(readLine()!.map { String($0) }.map{ Int($0)! })
  }
  
for _ in 0...N-1{
    B.append(readLine()!.map { String($0) }.map{ Int($0)! })
}

func flip(_ i:Int, _ j: Int) { //i, j 가 왼쪽 위 끝점으로 해서 3x3 행렬 만큼 뒤집는 함수
    for x in i..<i + 3 {
      for y in j..<j + 3{
          A[x][y] = 1 - A[x][y]
      }
    }
}

if N<3 || M<3 {
  if A != B {
    print(-1)
  }
  else{
    print(0)
  }
}
else{
  for i in 0..<N - 2{  // 줄바꿈 가능 횟수
      for j in 0..<M - 2{  // 가로 줄 이동 가능 횟수
          if A[i][j] != B[i][j]{
              flip(i, j)
              cnt += 1
          }
  
          if A == B{
              break
          }
      if A == B{
          break
      }
     }
  }
        
  if A != B{
    print(-1)
  }
  else{
    print(cnt)
  }
}

 

풀이

 

(그림이 ㅋㅋㅋ 죄송합니다... )

처음에 문제 설명과 예제에 따른 출력이 이해하기가 너무 힘들었다. 문장 그대로 이해하면 3x3 행렬을 행렬 A에서 이동하면서 3x3 범위의 총 9개의 원소가 모두 0->1 혹은 1->0으로 바꾸었을 때, B가 되는 최소값을 구하는 문제이다.

 

이 때 3x3 범위 내의 모든 요소를 0->1, 1->0으로 뒤집는 함수를 정의하면 다음과 같다.

func flip(_ i:Int, _ j: Int) { //i, j 가 왼쪽 위 끝점으로 해서 3x3 행렬 만큼 뒤집는 함수
    for x in i..<i + 3 {
      for y in j..<j + 3{
          A[x][y] = 1 - A[x][y] //1->0, 0->1
      }
    }
}

 

이렇게 뒤집었을 때 A에서 B로 바뀔 때, 바꾼 총 횟수를 세야하는데,

위 그림에서 알 수 있듯 5x5 행렬이라면 3x3 행렬을 가로로 (5-2=3)번, 세로로 (5-2=3)번 씩 움직일 수 있다.

바꾸는 시점은 행렬 A와 B에서 3x3 범위로 움직일 수 있는 범위 내(N-2, M-2)에 A의 왼쪽 위의 점 (i, j)이 B의 왼쪽 위의 점 (i, j)과 일치하지 않을때,  그때 한꺼번에 뒤집는다. 그리고 뒤집을 때마다 횟수에 +=1 을 해주었다.

  for i in 0..<N - 2{  // 줄바꿈 가능 횟수
      for j in 0..<M - 2{  // 가로 줄 이동 가능 횟수
          if A[i][j] != B[i][j]{
              flip(i, j)
              cnt += 1
          }
  
          if A == B{
              break
          }
      if A == B{
          break
      }
     }

 

바꾸면서 A와 B가 일치하게 되는 시점에 반복문을 탈출하고,  반복문을 다 돌았음에도 A와 B가 일치하지 않는다면 A로 B를 만들 수 없다는 것이므로 -1을 print하고, 그게 아니라면 횟수를 print 해주었다.

  if A != B{
    print(-1)
  }
  else{
    print(cnt)

 

여기서 중요한 것은, 행렬은 반드시 3x3 단위로 움직여야 하므로 N이나 M 둘 중 하나라도 3 미만이라면 당연히 3x3 행렬을 이용하여 B를 만들 수 없기 때문에 -1을 출력하도록 했고, 뒤집는 일련의 과정은 그게 아닐 경우에 동작하도록 했는데 60%에서 항상 틀렸다고 뜨는 불상사가 발생했다.

//처음 제출해서 60%에서 멈춘 코드
if N<3 || M<3 {
    print(-1)
}
else{
  for i in 0..<N - 2{  // 줄바꿈 가능 횟수
      for j in 0..<M - 2{  // 가로 줄 이동 가능 횟수
      ... 후략

 

엥? 당연히 가로와 세로 길이가 각각 3 미만이라면 3x3 행렬을 이용하여 A에서 B 행렬을 만들 수 없는게 당연한거 아닌가? 했는데

질문게시판에서 사례들을 보니 3 미만이라고 해서 무조건 -1을 호출하는 것이 아니라, 3 미만임에도 A와 B가 같다면 3x3 행렬의 연산을 수행을 하지 않아도 되므로 (횟수 0) 조건을 하나 더 걸어서 같은지를 따지도록 수정했다.

 

//바꾼 코드
if N<3 || M<3 {
  if A != B {
    print(-1)
  }
  else{
    print(0)
  }
}
else{
  for i in 0..<N - 2{  // 줄바꿈 가능 횟수
      for j in 0..<M - 2{  // 가로 줄 이동 가능 횟수