[프로그래머스] 프렌즈4블록

 

이 문제는 최근에 네이버 부스트 캠프 2차 코딩 테스트를 준비하기 위해 구현 문제를 찾아보던 중 하나인 "프렌즈 4블록" 문제를 풀어보게 되었습니다. 1차 합격 메일을 받았을 때 당시에 2박 3일 동안 동원 훈련 중이었기 때문에 휴대폰으로 문제를 풀기 위해 메모장을 사용하여 슈도코드를 작성하고 생각을 정리해 둔 문제였습니다.

 

이번 코드는 하나씩 설명하면 너무 길어지고 가독성이 좋지 않을 거 같아 최대한 코드 안에 코드의 역할을 적어보게 되었습니다.

---

1. 문제 링크 

 

프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/17679

 

2. 코드

func solution(_ m:Int, _ n:Int, _ board:[String]) -> Int {
    
    struct Tuple: Hashable{     //블록을 지우기 위해 위치 값
        let x : Int
        let y : Int
    }
    
    var lineUp : [[String]] = []   // 들어오는 값을 2차원 배열 보드판으로 만듬
    var blockIndex = Set<Tuple>()  // 제거해야하는 블록 위치 중복 안되게 저장
    var possible : Bool = true      // 4묶음 블록이 존재한다면 프로세스 진행
    var result : Int = 0            // 결과값 출력
    
    // MARK: lineUP 구성
    /// 2차원 배열으로 보드판 구성
    for j in Array(board){
        var temp : [String] = []
        for k in j{
            temp.append(String(k))
        }
        lineUp.append(temp)
    }
    
    // MARK: 4묶음 블록 찾기
    func findBlockIndex(){
        for i in 0..<lineUp.count{
            for j in 0..<lineUp[i].count{
                if lineUp[i][j] == "0"{     // 0은 빈칸이므로 checking할 필요 없이 패스
                    continue
                }
                checking(x: i, y: j, element: lineUp[i][j]) // 보드판 하나씩 전부 탐색
            }
        }
        
        // blockIndex.isEmpty가 비어있다는 뜻은 이젠 더 이상 4묶음 요소가 없어 while문을 종료해도 됨
        if blockIndex.isEmpty{
            possible = false    // while 끄기
        }
    }
    // MARK: 4묶음 확인
    /// 진행하고 있는 위치에서 오른쪽,아래, 대각선 값이 같은 요소인지 확인
    func checking(x: Int, y: Int, element: String) {
        let dx = [0,1,1]
        let dy = [1,0,1]

        for i in 0..<3{     //3번을 통해 오른쪽,아래,대각선 탐색
            if isValid(x: x+dx[i], y: y+dy[i]){
                // 탐색하는 위치 값의 요소가 전달받은 element이랑 다를시 return
                if lineUp[x+dx[i]][y+dy[i]] != element{
                    return
                }
            }else{      //범위를 벗어나도 return
                return
            }
        }
        
        possible = true //while문 반복하기 위해 true
        blockIndex.insert(Tuple(x: x, y: y))    //전달 받은 x,y값 제거를 할 blockIndex에 저장
        for i in 0..<3{
            if isValid(x: x+dx[i], y: y+dy[i]){
                blockIndex.insert(Tuple(x: x+dx[i], y: y+dy[i]))    // 탐색한 값도 저장
            }
        }
        return  //다음 순서로 진행을 위해
    }
    
    // MARK: 배열 범위 확인
    func isValid(x: Int, y: Int) -> Bool{
        // 범위안에 있다면 true, 아닐시 false
        if x < m && y < n {
            return true
        }
        return false
    }
    // MARK: 4묶음 요소 지우기
    func removeBlock(){
        // 저장해둔 블록 인덱스 값을
        for i in blockIndex{
            lineUp[i.x][i.y] = "0"      //지워야 하는 블록 값 "0"으로 바꾸기
        }
        result += blockIndex.count      //매판마다 지운 블록 수 result에 저장
        blockIndex = []     //매판마다 판단해야 하기 때문에 초기화
    }
    // MARK: 보드판 다시 만들기
    func rebuildingBlock(){
        // 보드판 배열의 인덱스를 거꿀로 조회하여 비어있는 부분 밑으로 내리기
        for i in stride(from: lineUp.count-1, through: 0, by: -1){
            for j in  stride(from: lineUp[i].count-1, through: 0, by: -1){
                if lineUp[i][j] != "0"{     // 확인하고 있는 요소의 값이 0이 아니라면 확인하기
                    movingDownBlock(x: i, y: j)
                }
            }
        }
       
    }
    // MARK: 블록 아래로 내리기
    func movingDownBlock(x: Int, y:Int){
        // 아래로 내리기 때문에 x+1 범위가 가능한지 확인
        if isValid(x: x+1, y: y){
            if lineUp[x+1][y] == "0"{   // 밑에 있는 칸이 "0" -> 비어있므로
                lineUp[x+1][y] = lineUp[x][y]   //밑에 칸에 지금 lineUp[x][y] 값 넣기
                lineUp[x][y] = "0"              //lineUp[x][y] 값을 빈칸으로 바꾸기
                movingDownBlock(x: x+1, y: y)   // 재귀를 통해 더 밑으로 내려갈 수 있는지 확인
            }
        }
        
    }
    
    // 반복을 통해 1. 4묶음 찾아 위치 인덱스 저장 2. 저장해둔 위치값 블록 지우기 3. 블록 재정비 -> 4묶음 없을 때까지 반복
    while possible{
        findBlockIndex()
        removeBlock()
        rebuildingBlock()
    }
    
    return result
}

 

3.  코드 설명

처음에는 4개의 블록을 어떻게 찾을 수 있을까 고민했는데, 보드를 2차원 배열로 만들어 길 찾기와 유사한 방식으로 접근하여 확인했습니다. 중복된 값은 Set을 이용하여 제외했습니다.

 

다음으로는 블록을 제거하고 아래로 내리는 방법에 대해 고민했습니다. 2차원 배열의 블록은 대부분 채워져 있기 때문에, 뒤에서부터 탐색하는 것이 더 효율적일 것이라 생각했습니다. 그래서 x 값만 고정된 상태에서 -1씩 내렸습니다.

 

마지막으로는 4개의 블록이 있는 동안에만 계속 진행해야 하는데, 각 판이 끝날 때마다 새로운 보드판이 생기기 때문에 어떻게 끝까지 확인할 수 있을까 고민했습니다. 이 부분에서 blockIndex.isEmpty를 이용하여 while문의 조건을 컨트롤했습니다.

 

이번에는 코드를 작성하며 메서드를 만들고 반환값을 고려하며 단계적으로 나누어서 문제를 해결하였습니다. 이 과정에서 코드를 조립하는 느낌이 들었고, 가독성이 좋아진 것 같아 레고처럼 조립하는 느낌이었습니다.