[PS][Programmers][Swift] 위클리 챌린지/3주차

올 상반기 모 기업의 입사 시험과 굉장히 흡...사 한데..
당시에 풀때도 대략 한시간 반정도를 공들여서 풀었던 기억이 난다.

그래프가 익숙하지않아서 중간에 C++로 바꿔서했다.. Swift 그래프 너무어렵...

총 소요 시간은 1시간 10분정도를 사용하였다.

내가 생각하는 난이도는 단순 구현 계산에 익숙한 사람이라면 정말 빠르고 쉽게 풀수 있을 것 같은데..
그래프를 손놓은지 오래되서 그런지 빠르고 정확하게 풀이하는게 순간적으로 어려워져서 애먹었다.

내가 생각한 논리는 단순하지만 비효율적이다.

1. Table 에서 사용할수 있는 블록들에 플러드 필을 사용하여 사용할 블록들의 넘버링을 한다.

2. 넘버링이 되었다면, 해당 테이블에 대해 돌린 테이블을 추가적으로 기록해두고, 블록의 갯수에 대해서도 기록해 둔다.

3. 회전이 되었고, 넘버링이 되어있는 Table에 대하여 첫 시작에 대한 움직임에 대한 Queue를 기록해둔다.

   이 부분이 중요한데, 마냥 direction만 기록해두면 같지 않음에도 똑같이 direction 배열이 나올수밖에 없다. 나는 이렇게 해도 메모리 사용 제한이 크지 않음을 알기에 블록의 움직임 순서에 따른 sequence를 기록해두었다.

4. 사용하게 될 game_board를 (0,0) -> (N-1, N-1) 로 순차 탐색하면서 블록이 들어갈 수 있는 영역에 대하여 탐색을 시작한다.

5. 탐색 시 들어갈수 있는 블록의 갯수가 같은 것들을 가능성 있는 블록이라고 판단하여 해당 블록에 대해서 2, 3번에서 탐색해 두었던 넘버링과 탐색시 첫 블록에 대한 움직임 Queue를 비교한다.

6. 5번에서의 결과가 맞다면 블록의 갯수를 덧셈연산하여 최종 리턴을 해준다.

코드로서 풀이는 다음과 같다.

import Foundation
var visit: [[Bool]] = []
var cntOfcnt: [Int] = [0]
var dq: [[[[Int]]]] = [[[[Int]]]]()//direction Queue
let dx = [0,0,1,-1]
let dy = [1,-1,0,0]
func fill(_ x: Int, _ y: Int, _ rotate: inout [[[Int]]], _ cnt: Int ) {
    cntOfcnt.append(1)
    var q: [(Int, Int)] = []
    var front = 0
    q.append((x, y))
    visit[x][y] = true
    rotate[0][x][y] = cnt
    while front != q.count {
        let xy = q[front]
        front += 1
        for i in 0..<4 {
            let delta = (xy.0 + dx[i], xy.1 + dy[i])
            if delta.0 >= 0, delta.0 < rotate[0].count, delta.1 >= 0, delta.1 < rotate[0].count {
                if visit[delta.0][delta.1] == false, rotate[0][delta.0][delta.1] == 1 {
                    visit[delta.0][delta.1] = true
                    rotate[0][delta.0][delta.1] = cnt
                    q.append(delta)
                    cntOfcnt[cnt] += 1
                }
            }
        }
    }
}

func findDir(_ rotate: [[[Int]]], _ index: Int, _ posi: Int, _ x: Int, _ y: Int) {
    let p = posi
    visit[x][y] = true
    var front = 0
    var q: [(Int, Int)] = [(x,y)]
    var countt = 0
    while front != q.count {
        let xy = q[front]
        front += 1
        dq[index][posi].append([Int]())
        for i in 0..<4 {
            let delta = (xy.0 + dx[i], xy.1 + dy[i])
            if delta.0 >= 0, delta.0 < rotate[0].count, delta.1 >= 0, delta.1 < rotate[0].count {
                if visit[delta.0][delta.1] == false, rotate[index][delta.0][delta.1] == p {
                    visit[delta.0][delta.1] = true
                    dq[index][posi][countt].append(i)
                    q.append(delta)
                }
            }
        }
        countt += 1
    }
}

func findNB(_ board:[[Int]], _ x: Int, _ y: Int)->(Int, [[Int]]) {
    var comp : [[Int]] = []
    var cntt = 0
    var coc = 1
    var q: [(Int, Int)] = [(x, y)]
    var front = 0
    visit[x][y] = true
    while front != q.count {
        let xy = q[front]
        front += 1
        comp.append([Int]())
        for i in 0..<4 {
            let delta = (xy.0 + dx[i], xy.1 + dy[i])
            if delta.0 >= 0, delta.0 < board[0].count, delta.1 >= 0, delta.1 < board[0].count {
                if visit[delta.0][delta.1] == false, board[delta.0][delta.1] == 0 {
                    visit[delta.0][delta.1] = true
                    comp[cntt].append(i)
                    q.append(delta)
                    coc += 1
                }
            }
        }
        cntt += 1
    }
    return (coc, comp)
}

func calc(_ input: (Int, [[Int]]), _ ct: Int)->Bool {
    for iii in 0..<4 {
        for ccc in 0..<ct {
            if cntOfcnt[ccc] == input.0 {
                if dq[iii][ccc] == input.1 {
                    cntOfcnt[ccc] = 0
                    return true
                }
            }
        }
    }
    return false
}
func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {
    var rotate : [[[Int]]] = [[[Int]]](repeating: table, count: 4)
    var cnt = 1
    let layer : [Bool] = [Bool](repeating: false, count: rotate[0][0].count)
    visit = [[Bool]](repeating: layer, count: rotate[0].count)
    for i in 0..<rotate[0].count {
        for j in 0..<rotate[0][i].count {
            if rotate[0][i][j] == 1, visit[i][j] == false{
                fill(i, j, &rotate, cnt)
                cnt += 1
            }
        }
    }
    let l2 = [[Int]]()
    let l3 = [[[Int]]](repeating: l2, count: cnt)
    dq = [[[[Int]]]](repeating: l3, count: 4)
    
    for i in 1..<4 {
        for j in 0..<rotate[i].count {
            for k in 0..<rotate[i][j].count {
                rotate[i][j][k] = rotate[i - 1][table.count - 1 - k][j]
            }
        }
    }

    for i in 0..<4 {
        visit = [[Bool]](repeating: layer, count: rotate[0].count)
        for j in 0..<rotate[i].count {
            for k in 0..<rotate[i][j].count {
                if rotate[i][j][k] != 0, visit[j][k] == false {
                    findDir(rotate, i,rotate[i][j][k], j, k)
                }
            }
        }
    }
    visit = [[Bool]](repeating: layer, count: rotate[0].count)
    var ans = 0
    for i in 0..<game_board.count {
        for j in 0..<game_board[i].count {
            if game_board[i][j] == 0, visit[i][j] == false {
                let ret = findNB(game_board, i, j)
                if ret.0 > 6 { continue }
                if calc(ret, cnt) {ans += ret.0}
                
                
            }
        }
    }
    
    return ans
}

아쉬운 점

1. 내용은 생각보다 간단한데 swift로 그래프를 구현하는게 익숙하지가 않아서 상당히 헷갈리고 많이 애를 먹었다.

2. 움직임을 나타내는 dq(direction queue)는 심지어 4차원 배열로 잡았다;;

3. 의미를 나만 알수있게 설정해놓은 변수명이 너무 많다.

오늘의 잘못을 반성하여 내일 더 나은 내가 되도록 하자.