[Algorithm]BOJ_14500_테트로미노_Go

문제 링크

BOJ_14500_테트로미노

문제 풀이

1. 테트리스의 블럭은 연속된 4개의 1X1 블럭의 조합임을 이해
2. 1의 이유로 그래프를 통해 풀이 가능
3. 백트래킹을 이용한 풀이로 가지치기가 가능한 재귀를 사용하는 DFS를 활용
4. T모양의 경우 dfs로 표현이 불가능. 따로 확인을 해주어야함. (하드코딩활용..)

package q14500

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var M, N int

var dx = [3]int{-1, 0, 1}
var dy = [3]int{0, 1, 0}
var mmap [][]int
var visited [][]bool
var max int
var tmp int

func dfsForFindMaxVal(row, col, cnt int) {
    if cnt == 4 {
        if max < tmp {
            max = tmp
        }
        return
    }
    nowRow := row
    nowCol := col
    for i := 0; i < 3; i++ {
        nextRow := nowRow + dy[i]
        nextCol := nowCol + dx[i]
        if isRightRange(nextRow, nextCol) && visited[nextRow][nextCol] == false {
            visited[nextRow][nextCol] = true
            tmp += mmap[nextRow][nextCol]
            dfsForFindMaxVal(nextRow, nextCol, cnt+1)
            tmp -= mmap[nextRow][nextCol]
            visited[nextRow][nextCol] = false
        }
    }
}

func checkT() {
    var tShape int
    for r := 0; r < M-2; r++ {
        for c := 0; c < N-2; c++ {
            plusShape := 0
            plusShape += mmap[r][c+1]
            plusShape += mmap[r+1][c]
            plusShape += mmap[r+1][c+1]
            plusShape += mmap[r+1][c+2]
            plusShape += mmap[r+2][c+1]
            tShape = plusShape
            tShape -= mmap[r][c+1]
            if tShape > max {
                max = tShape
            }
            tShape = plusShape
            tShape -= mmap[r+1][c]
            if tShape > max {
                max = tShape
            }
            tShape = plusShape
            tShape -= mmap[r+1][c+2]
            if tShape > max {
                max = tShape
            }
            tShape = plusShape
            tShape -= mmap[r+2][c+1]
            if tShape > max {
                max = tShape
            }
        }
    }
    for r := 0; r < M-2; r++ {
        tShape := 0
        tShape += mmap[r][N-1]
        tShape += mmap[r+1][N-1]
        tShape += mmap[r+2][N-1]
        tShape += mmap[r+1][N-2]
        if tShape > max {
            max = tShape
        }
    }
    for r := 0; r < M-2; r++ {
        tShape := 0
        tShape += mmap[r][0]
        tShape += mmap[r+1][0]
        tShape += mmap[r+2][0]
        tShape += mmap[r+1][1]
        if tShape > max {
            max = tShape
        }
    }
    for c := 0; c < N-2; c++ {
        tShape := 0
        tShape += mmap[M-1][c]
        tShape += mmap[M-1][c+1]
        tShape += mmap[M-1][c+2]
        tShape += mmap[M-2][c+1]
        if tShape > max {
            max = tShape
        }
    }
    for c := 0; c < N-2; c++ {
        tShape := 0
        tShape += mmap[0][c]
        tShape += mmap[0][c+1]
        tShape += mmap[0][c+2]
        tShape += mmap[1][c+1]
        if tShape > max {
            max = tShape
        }
    }
}

func isRightRange(r, c int) bool {
    if r >= 0 && r < M && c >= 0 && c < N {
        return true
    }
    return false
}

func stringToInt(str string) int {
    val, _ := strconv.Atoi(str)
    return val
}

func Start() {
    fmt.Scan(&M, &N)
    mmap = make([][]int, M)
    visited = make([][]bool, M)
    for i := range mmap {
        mmap[i] = make([]int, N)
        visited[i] = make([]bool, N)
    }
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)
    for row := range mmap {
        for col := range mmap[row] {
            scanner.Scan()
            mmap[row][col] = stringToInt(scanner.Text())
        }
    }
    for row := 0; row < M; row++ {
        for col := 0; col < N; col++ {
            visited[row][col] = true
            tmp += mmap[row][col]
            dfsForFindMaxVal(row, col, 1)
            tmp -= mmap[row][col]
            visited[row][col] = false

        }
    }
    checkT()
    fmt.Println(max)
}

왜 이제 코테가 JAVA로만 풀 수 있게 바뀌는지 모르겠다.. 물론 기업입장에서는 주 언어의 활용 능력을 확인하는게 맞지만.. Go 공부하고 싶은데 내가 잘하고 있는것인지 무섭다. JAVA, Spring.....ㅡㅜ