Swift) 백준 14500번 테트로미노 - G4

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

14500번: 테트로미노

배열 + 최대의 합을 구하라는 시점에 완전 탐색을 써야한다는건 알았지만, 테트로미노를 어떤식으로 해야 할지 많이 고민했던 문제.

테트로미노의 모양을 모두 시작점을 기준으로 하드코딩 해서 하는 방법도 생각했지만... 그런식으로는 풀기 싫어서 다른 방법을 생각했다.

테트로미노의 모양은 ㅗ 모양을 제외하고 모두 DFS로 정의 할 수 있음. 따라서 시작점을 기준으로 dfs로 경로값을 계산 후 ㅗ 모양은 따로 하드코딩방식으로 좌표값을 계산하는 방식으로 문제를 풀음.

 

이 방식으로 하면 중복되는 경로를 재탐색하는 경우도 많기에 입출력이 많으면 시간초과가 떴을듯..

import Foundation


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

var map: [[Int]] = []
var answer = 0

for _ in 0..<input[0] {
    map.append(readLine()!.split(separator: " ").map { Int($0)! })
}

var visited:[[Bool]] = Array(repeating: Array(repeating: false, count: m), count: n)
let dx = [1, -1, 0, 0]
let dy = [0, 0, 1, -1]

func checkShape(x: Int, y: Int, depth: Int, sum: Int) {
    if depth == 4 {
        answer = max(sum, answer)
        return
    }
    for i in 0..<4 {
        let nx = x+dx[i]
        let ny = y+dy[i]
        
        if nx < 0 || nx >= m || ny < 0 || ny >= n {
            continue
        }
        if !visited[ny][nx] {
            visited[ny][nx] = true
            checkShape(x: nx, y: ny, depth: depth+1, sum: sum + map[ny][nx])
            visited[ny][nx] = false
        }
    }
}
let oShapeX: [[Int]] = [[1,2,1],[1,2,1],[0,0,1],[0,0,-1]]
let oShapeY: [[Int]] = [[0,0,1],[0,0,-1],[1,2,1],[1,2,1]]

func checkOShape(x: Int, y: Int, currentValue: Int) {
    for i in 0..<4 {
        var sum = currentValue
        var flag = false
        for j in 0..<3 {
            let nx = x+oShapeX[i][j]
            let ny = y+oShapeY[i][j]
            if nx < 0 || nx >= m || ny < 0 || ny >= n {
                flag = true
                break
            }
            sum += map[ny][nx]
        }
        if !flag {
            answer = max(answer, sum)
        }
    }
}

func solution() {
    for i in 0..<n {
        for j in 0..<m {
            visited[i][j] = true
            checkShape(x: j, y: i, depth: 1, sum: map[i][j])
            checkOShape(x: j, y: i, currentValue: map[i][j])
            visited[i][j] = false
        }
    }
}

solution()
print(answer)