[Swift Algorithm] 테트로미노 BOJ #14500

문제

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

14500번: 테트로미노

 

내 문제 풀이

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = input[0]
let m = input[1]
var paper = [[Int]]()
var result = 0

for _ in 0..<n { paper.append(readLine()!.split(separator: " ").map{Int(String($0))!}) }

func check(_ x: Int, _ y :Int, _ before: Int, _ count: Int, _ sum: Int) {
    if count == 4 { result = max(result, sum); return }

    if x-1 >= 0 && before != 1 { check(x-1, y, 2, count+1, sum+paper[x-1][y]) }
    if x+1 < n && before != 2 { check(x+1, y, 1, count+1, sum+paper[x+1][y]) }
    if y-1 >= 0 && before != 3 { check(x, y-1, 4, count+1, sum+paper[x][y-1]) }
    if y+1 < m && before != 4 { check(x, y+1, 3, count+1, sum+paper[x][y+1]) }
}

func checkSpecial(_ x: Int, _ y: Int) {
    // 'ㅗ', 'ㅜ'
    if x+1 < n && y-1 >= 0 && y+1 < m {
        result = max(result, max(paper[x][y] + paper[x+1][y-1] + paper[x+1][y] + paper[x+1][y+1], paper[x][y] + paper[x][y-1] + paper[x+1][y] + paper[x][y+1]))
    }
    
    // 'ㅏ', 'ㅓ'
    if x+2 < n && y+1 < m {
        result = max(result, max(paper[x][y] + paper[x+1][y] + paper[x+1][y+1] + paper[x+2][y], paper[x+1][y] + paper[x][y+1] + paper[x+1][y+1] + paper[x+2][y+1]))
    }
}

for i in 0..<n {
    for j in 0..<m {
        check(i, j, 0, 1, paper[i][j])
        checkSpecial(i, j)
    }
}

print(result)

👉 dp를 사용하여 풀어주었음. 테트로미노들의 특성(?)을 파악하고, 잘 이용해주어야 하는 것이 포인트

 

[ 개념 정리 ]

문제에 주어진 그림을 보면,

'ㅗ' 모양의 테트로미노를 제외한 나머지 테트로미노들은 중복없이 모든 정사각형을 지날 수 있지만

'ㅗ' 모양의 경우 중복을 피할 수 없다.

예를들어 1번 정사각형부터 이동한다고 하면, 1 -> 2 -> 4 -> 2 -> 3 이런 식으로 꼭 중복이 생긴다.

따라서 'ㅗ' 모양을 제외하고는 모두 중복 없이 네 정사각형이 위치하는 값들의 최대 합을 구할 수 있다.

(처음에는 dfs로 풀었지만 dfs로 풀 시에는 모든 모양에 있어서 중복을 제외할 수 없기에 시간초과가 발생했다.)

=> 'ㅗ' 모양의 테트로미노는 예외로 구해주고, 나머지 모양들은 dp를 통해 효율적으로 확인할 수 있다.

 

[ 문제 풀이 ]

• check 함수의 파라미터를 먼저 설명해보자면 x와 y는 탐색을 시작하는 좌표의 위치이고,
  count는 몇 개의 블록을 지났는지 카운트, sum의 경우에는 블록을 지나며 더한 값을 의미한다.
  before는 가장 중요한 인자라고 생각하는데,
  이 재귀함수가 이번엔 어떤 방향으로 움직인건지를 나타내주어 중복을 피하게 한다.
  예를 들어, before가 1이라면 이전 좌표에서 한 칸 위로 올라왔다는 것을 뜻한다. 
  따라서 다음에 탐색할 때는 다시 아래로 한 칸 내려가는 것은 중복인 것을 알 수 있고, 피할 수 있다.
• check 함수는 before 인자에 따라서 알맞은 재귀함수를 호출해주고,
  또 count가 4가 됐을 때는 result 값과 sum 값 중 더 큰 값을 result에 저장한 후 리턴한다.
• checkSpecial 함수는 'ㅗ' 모양의 테트로미노들을 찾는 역할을 한다.
  'ㅗ' 모양은 위에서 말했듯이 중복을 피하면 절대 찾을 수 없는 모양이므로 이렇게 예외로 처리한다.
  'ㅗ', 'ㅜ', 'ㅏ', 'ㅓ' 이렇게 총 네 가지만 확인하면 되므로, 재귀호출 할 필요 없이 일일히 확인해주었다.

 

💡 피드백

• 처음에는 어떻게 풀어야 할지 아예 감을 못잡아서 어떻게 접근해야 할지에 대해서만 찾아보고 풀었는데,
  중복을 생각하지 못하고 dfs로 풀었다가 시간초과였고,, 그래서 또 다시 풀었다.
• 'ㅗ' 모양만 제외하면 중복 없이 확인할 수 있다는 부분만 캐치하면 크게 어려운 문제는 아닌 것 같지만
  어쨌든 시간이 오래걸렸다,, 다음에 다시 한 번 풀어봐야 하는 문제같다.