[Algorithm/BOJ] 14500 - 테트로미노 Swift Python

문제 풀이: 

모든 도형을 일일이 회전하고 싶지 않아서 고민을 하다가 인터넷에서 접근 방법만 확인하고 풀었다.

ㅜ, ㅏ, ㅗ, ㅓ를 제외한 모든 도형은 dfs로 해결할 수 있다는 것을 깨달았다.

ㅜ 형태의 테트로미노는 (0,0)을 기준으로 다음 그림과 같이 만들 수 있다.

한 좌표를 기준으로 dfs로 ㅜ형태의 테트로미노를 제외한 모든 도형의 최댓값을 갱신하고

ㅜ형태의 테트로미노를 따로 계산하여 최댓값을 갱신하면 된다.

 

코드:

Swift

typealias Coord = (r: Int, c: Int)

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nm[0]
let m = nm[1]
var paper = [[Int]]()
var check = [[Bool]](repeating: [Bool](repeating: false, count: m), count: n)

let d: [Coord] = [(-1,0),(0,-1),(1,0),(0,1)]
// ㅜ, ㅏ, ㅗ, ㅓ
let exD: [[Coord]] = [
    [(0,0),(0,1),(0,2),(1,1)],
    [(0,0),(1,0),(2,0),(1,1)],
    [(0,0),(0,1),(0,2),(-1,1)],
    [(0,0),(0,1),(-1,1),(1,1)]
]
var res = 0

// 'ㅜ'를 제외한 테트로미노 최댓값 구하기
func dfs(_ cnt: Int, _ sum: Int, _ r: Int, _ c: Int) {
    if cnt == 4 {
        res = max(res, sum)
        return
    }
    
    for i in 0 ..< 4 {
        let nr = r + d[i].r
        let nc = c + d[i].c
        
        guard 0 <= nr && nr < n && 0 <= nc && nc < m else { continue }
        
        if check[nr][nc] == false {
            check[nr][nc] = true
            dfs(cnt+1, sum+paper[nr][nc], nr, nc)
            check[nr][nc] = false
        }
    }
}

// 'ㅜ' 형태의 테트로미노 최댓값 구하기
func checkExcluded(_ r: Int, _ c: Int) {
    // ㅜ,ㅓ,ㅏ,ㅗ 네 가지 모두 구하기
    for i in 0 ..< 4 {
        var sum = 0
        var isComplete = true
        for j in 0 ..< 4 {
            let nr = r + exD[i][j].r
            let nc = c + exD[i][j].c
            
            // ㅗ,ㅓ,ㅏ,ㅗ 중 한 형태가 완성될 수 없을 때
            guard 0 <= nr && nr < n && 0 <= nc && nc < m else {
                isComplete = false
                break
            }
            sum += paper[nr][nc]
        }
        if isComplete == true {
            res = max(res, sum)
        }
    }
}

func solution() {
    for _ in 0 ..< n {
        paper.append(readLine()!.split(separator: " ").map { Int(String($0))! })
    }
    
    for r in 0 ..< n {
        for c in 0 ..< m {
            check[r][c] = true
            dfs(0, 0, r, c)
            check[r][c] = false
            
            checkExcluded(r, c)
        }
    }
    print(res)
}

solution()

 

Python 

# 테트로미노 / 구현
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(n)]
check = [[0] * m for _ in range(n)]
d = [[-1,0],[0,-1],[1,0],[0,1]]
ex_d = [
    [(0,0),(0,1),(0,2),(1,1)],
    [(0,0),(1,0),(2,0),(1,1)],
    [(0,0),(0,1),(0,2),(-1,1)],
    [(0,0),(0,1),(-1,1),(1,1)]
]
res = 0

def dfs(cnt, sum, r, c):
    global res, check
    if cnt == 4:
        res = max(res, sum)
        return
    
    for i in range(4):
        nr = r + d[i][0]
        nc = c + d[i][1]
        if 0 <= nr < n and 0 <= nc < m and not check[nr][nc]:
            check[nr][nc] = 1 
            dfs(cnt+1, sum+paper[nr][nc], nr, nc)
            check[nr][nc] = 0

def checkExcluded(r, c):
    global res
    for i in range(4):
        sum = 0
        isComplete = 1
        for j in range(4):
            nr = r + ex_d[i][j][0]
            nc = c + ex_d[i][j][1]

            if 0 <= nr < n and 0 <= nc < m:
                sum += paper[nr][nc]
            else:
                isComplete = 0
                break
        if isComplete:
            res = max(res, sum)

def solution():
    for r in range(n):
        for c in range(m): 
            check[r][c] = 1
            dfs(0,0,r,c)
            check[r][c] = 0

            checkExcluded(r,c)
    print(res)

solution()

 

문제:

14500번: 테트로미노