[백준] (Swift) 14500번 - 테트로미노 (완전탐색 / DFS로도 풀 수 있다던데?)

나는 해당 문제를 완전탐색으로 풀었다. 감히 DFS는 생각해내지도 못함,,,
완전 탐색으로 모든 모양에 대한 함수를 따로 작성하고 풀어서 코드가 무려 287줄이나 나왔다. ㅋㅋㅋㅋ(주석포함)
구현실력도 중요하지만, 오답노트는 꼭 DFS로 해보자.👊🏻

 

🟠 문제

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

14500번: 테트로미노

 

🟠 나의 풀이

이것도 예전에 스터디할 때 한 번 봤던 문제다. 그래서, 모든 경우를 다 살펴봐야한다는 사실을 알고 있었다. (완전탐색(브루트포스)문제이기도하고!) 그래서 그냥,, 보자마자 숨이 턱 막혔지만, 구현해보기로 했다.

테트리스 조각은 다섯개가 있다. 해당 다섯개 모양은 회전도 가능하고, 대칭도 가능했다. 회전이야 for 문으로 돌리면 된다고 생각했고 대칭은 따로 만들어서 새로운모양으로 다뤄줘야겠다고 판단했다.

내가 풀이한 방법의 가장 핵심은 한칸식 색칠해준다는 식으로 접근했다.

앞서 bfs문제를 풀듯 dx, dy 방향키를 설정해두자. ㅡ 모양을 예시로 들면,  for문을 4번 돌려서 오른쪽칸을 하나씩 해당 위치에 있는 내부의 수를 더해주면 된다.

그럼 L 모양처럼 꺾인건 어떻게 할까?

이렇게 하면 된다. 즉, 방향전환이 한번 필요하다. 지금 해당 L을 보면, 오른쪽으로 색칠이 되다가, 방햐잉 '위'로 바뀌어야한다. 이것을 나는 direction이라고 따로 지정해주었다. 내가 지정해준 방향키로 보면, '오른쪽'은 dx,dy인덱스 3이다. 3방향으로 진행하다가, 0 방향으로 바꿔주면 된다. 

도형의 회전도 마찬가지다. 도형을 회전하는 것도, 색칠하는 방향으로 생각하면된다. 오른쪽으로 가면서 색칠하다가, 방향을 바꿔서 위로 가면서 색칠하고, 또 방향을 바꿔서 왼쪽으로 가면서 색칠하고,, 이런식으로 생각하면된다!

머릿속에서 그림을 그린다고 생각하고 회전하면서 ,, 그리면서,, 풀었다. 🤯🤯🤯🤯

🔖 추가로, 대칭이 필요한 도형은 무엇이 있을까?

대칭이 필요한 도형은, L모양과 Z 모양 두개 뿐이었다. l 모양, ㅁ모양, ㅏ모양은 회전으로 모든 모양이 가능하다. ㅏ는 오른쪽으로 대칭하면 ㅓ모양이지만, 간단하게 생각하면 ㅏ를 두번 회전하면 ㅓ가 나온다. 그래서 따로 대칭에 대한 func은 생각하지 않아도 된다.

이 모든것들을 구현해보자...

 

🟠 정답코드

시간초는 2초가 주어졌다. 총 2억번 돌아갈 수 있다. 완전탐색으로 풀어도 시간은 충분하다

import Foundation

// 필요한 변수 선언
let nm = readLine()!.split(separator: " ").map{ Int($0)! }
var tetroMap = [[Int]]()
for _ in 0..<nm[0] {
    let temp = readLine()!.split(separator: " ").map { Int($0)! }
    tetroMap.append(temp)
}

// 위 아래 왼 오
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

// 테트로미노 모양별 합을 구해주는 func
// 대칭이 필요한 녀석은 L 과 Z
// 1. ㅡ
private func tetro_1(direction: Int, nx: Int, ny: Int) -> Int {
    var nx = nx
    var ny = ny
    var total = 0
    for _ in 0..<4 {
        if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
            return 0
        }
        total += tetroMap[nx][ny]
        nx += dx[direction]
        ny += dy[direction]
    }
    return total
}

// 2. ㅁ
private func tetro_2(direction: Int, nx: Int, ny: Int) -> Int {
    var total = 0
    if nx < 0 || ny < 0 || nx+1 >= nm[0] || ny+1 >= nm[1] {
        return 0
    }
    total += tetroMap[nx][ny]
    total += tetroMap[nx+1][ny]
    total += tetroMap[nx][ny+1]
    total += tetroMap[nx+1][ny+1]
    return total
}

// 3. L의 대칭
private func tetro_3(direction: Int, nx: Int, ny: Int) -> Int {
    var direction = direction
    var nx = nx
    var ny = ny
    var total = 0

    for _ in 0..<3 {
        if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
            return 0
        }
        total += tetroMap[nx][ny]
        nx += dx[direction]
        ny += dy[direction]
    }

    nx -= dx[direction]
    ny -= dy[direction]

    if direction == 3 {
        direction = 1
    } else if direction == 0 {
        direction = 3
    } else if direction == 2 {
        direction = 0
    } else {
        direction = 2
    }

    nx += dx[direction]
    ny += dy[direction]
    if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
        return 0
    }
    total += tetroMap[nx][ny]
    return total
}

// 3.1 L
private func tetro_3_symmetry(direction: Int, nx: Int, ny: Int) -> Int {
    var direction = direction
    var nx = nx
    var ny = ny
    var total = 0

    for _ in 0..<3 {
        if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
            return 0
        }
        total += tetroMap[nx][ny]
        nx += dx[direction]
        ny += dy[direction]
    }
    nx -= dx[direction]
    ny -= dy[direction]

    if direction == 3 {
        direction = 0
    } else if direction == 0 {
        direction = 2
    } else if direction == 2 {
        direction = 1
    } else {
        direction = 3
    }

    nx += dx[direction]
    ny += dy[direction]
    if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
        return 0
    }
    total += tetroMap[nx][ny]
    return total
}

// 4. Z
private func tetro_4(direction: Int, nx: Int, ny: Int) -> Int {
    var direction = direction
    var nx = nx
    var ny = ny
    var total = 0

    for _ in 0..<2 {
        if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
            return 0
        }
        total += tetroMap[nx][ny]
        nx += dx[direction]
        ny += dy[direction]
    }
    nx -= dx[direction]
    ny -= dy[direction]

    if direction == 3 {
        direction = 1
    } else if direction == 0 {
        direction = 3
    } else if direction == 2 {
        direction = 0
    } else {
        direction = 2
    }
    nx += dx[direction]
    ny += dy[direction]
    if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
        return 0
    }
    total += tetroMap[nx][ny]

    if direction == 1 {
        direction = 3
    } else if direction == 3 {
        direction = 0
    } else if direction == 0 {
        direction = 2
    } else {
        direction = 1
    }
    nx += dx[direction]
    ny += dy[direction]
    if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
        return 0
    }
    total += tetroMap[nx][ny]
    return total
}

// 4.1 Z의 대칭
private func tetro_4_symmetry(direction: Int, nx: Int, ny: Int) -> Int {
    var direction = direction
    var nx = nx
    var ny = ny
    var total = 0

    for _ in 0..<2 {
        if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
            return 0
        }
        total += tetroMap[nx][ny]
        nx += dx[direction]
        ny += dy[direction]
    }
    nx -= dx[direction]
    ny -= dy[direction]

    if direction == 3 {
        direction = 0
    } else if direction == 0 {
        direction = 2
    } else if direction == 2 {
        direction = 1
    } else {
        direction = 3
    }
    nx += dx[direction]
    ny += dy[direction]
    if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
        return 0
    }
    total += tetroMap[nx][ny]

    if direction == 0 {
        direction = 3
    } else if direction == 2 {
        direction = 0
    } else if direction == 1 {
        direction = 2
    } else {
        direction = 3
    }
    nx += dx[direction]
    ny += dy[direction]
    if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
        return 0
    }
    total += tetroMap[nx][ny]
    return total
}

// 5. ㅗ ㅜ ㅏ ㅓ
private func tetro_5(direction: Int, nx: Int, ny: Int) -> Int {
    var direction = direction
    var nx = nx
    var ny = ny
    var total = 0

    for _ in 0..<3 {
        if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
            return 0
        }
        total += tetroMap[nx][ny]
        nx += dx[direction]
        ny += dy[direction]
    }
    nx = nx - dx[direction] - dx[direction]
    ny = ny - dy[direction] - dy[direction]

    if direction == 3 {
        direction = 1
    } else if direction == 0 {
        direction = 3
    } else if direction == 2 {
        direction = 0
    } else {
        direction = 2
    }
    nx += dx[direction]
    ny += dy[direction]
    if nx < 0 || ny < 0 || nx >= nm[0] || ny >= nm[1] {
        return 0
    }
    total += tetroMap[nx][ny]
    return total
}

// main
var direction = 0
var answer = [Int]()

for i in 0..<nm[0] {
    for j in 0..<nm[1] {
        // 4방향 돌리기
        for k in 0..<4 {
            answer.append(tetro_1(direction: k, nx: i, ny: j))
            answer.append(tetro_2(direction: k, nx: i, ny: j))
            answer.append(tetro_3(direction: k, nx: i, ny: j))
            answer.append(tetro_3_symmetry(direction: k, nx: i, ny: j))
            answer.append(tetro_4(direction: k, nx: i, ny: j))
            answer.append(tetro_4_symmetry(direction: k, nx: i, ny: j))
            answer.append(tetro_5(direction: k, nx: i, ny: j))
        }
    }
}

print(answer.max()!)

 

 

아오,, 길고 길다.. 생각한것처럼 코드만 잘~~~~ 짜여지면 통과할 수 있는 문제다. 근데,,, 이방향 저방향 헷갈려서 풀기 쉽지 않았다. 하지만, 코드를보면 초반에 감을 잡으면 뒤에 함수들은 거의다 똑같이 흘러간다. 초반에 감잡는데 조금 오래걸렸고, 뒤에 함수들은 복붙하면서 머리로 슉슉 그림을 그리면서 풀었다. 

생각보다 코테에서 마주쳤을때, 다른 알고리즘 문제들을 푸는것보다 구현하는 문제가 가장 힘들다. 머리로 그림을 그려나가는게 생각보다 힘이들고, 이것을 코드로 그대로 구현하는것도 상당한 생각이 필요하다. 이 문제를 푸는 것은 상당히 귀찮은 일이라고 생각햇지만 이런류의 문제를 많이 마주치면, 확실히 코테 대비가 잘 될 것 같다. (이 문제랑 비슷한 문제를 LG CNS 코테에서 본적이 잇는것같다. 그 문제도 결국 구현문제였긴했었는데,,, ) 

화이팅,,그리고 모두 해피뉴이어어ㅓ