[Swift 알고리즘] 백준 2578 (빙고)

 

인프런 2021 개발자 빙고...

 

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

2578번: 빙고

 

 

 

 

해결 방법 : 부른 자리에서 상 하 좌 우로 dfs를 통해 계산합니다. 아래는 isBing이라는 dfs 함수입니다. axis와 vector라는 파라미터로 row혹은 col로, 양수 방향 혹은 음수 방향으로 갈 지를 정합니다. 

 

 

 

func isBing(_ rowVal: Int, _ colVal: Int, _ axis: Int, _ vector: Int) -> Bool { //axis 0이면 row 1이면 col
    if rowVal < 0 || rowVal > 4 || colVal < 0 || colVal > 4 {
    //만약 rowVal이나 colVal이 음수이거나 4보다 클 경우 depth끝까지 온 것이다.
        return true
    }
    var tempBing = false
    if bingArr[rowVal][colVal] == 0 { //만약 트레벌스 하는 점이 0일 경우에는 depth끝까지 뒤진다.
        if axis == 0 { //탐색 방향이 row방향인지 아닌지 검사한다.
            tempBing = isBing(rowVal + 1 * vector, colVal, axis, vector)
            //row방향으로 탐색하는데 vector라는 방향을 주어서 음수 ind 혹은 양수 ind로 탐색한다.
        }
        else if axis == 1 { //탐색방향이 col방향이다.
            tempBing = isBing(rowVal, colVal + 1 * vector, axis, vector)
        }
    }
    return tempBing //true일 경우 그 점에서 가로 혹은 세로로 빙고가 된다.
}

 

특정상황에서는 대각선이 빙고인지 확인해야 합니다. 따라서 대각선일때를 고려해야 합니다. 대각선일때는 rowVal 과 colVal이 같을 경우와 4 - rowVal 과 colVal이 같을 경우 를 나눠서 계산합니다.

func checkCross(_ pos: Int)-> Int { //1일때는 0 1 2 3 4 
    var count = 0
    if pos >= 0 {
        for i in 0...4 {
            if bingArr[i][i] == 0 {continue}
            else {return count}
        }
        count += 1
    }
    else if pos <= 0 {
        for i in 0...4 {
            if bingArr[4 - i][i] == 0 {continue}
            else {return count}
        }
        count += 1
    }
    return count 
}

 

현재 점이 어느위치에 있는지 알아야 하기 때문에 hashMap을 활용합니다.

var hash: [Int: [Int]] = [:]
for i in 0 ..< 5 {
    for j in 0 ..< 5 {
        hash[bingArr[i][j]] = [i, j]
    }
}

 

hashMap을 통해 현재 점이 빙고인지 아닌지 확인합니다.

 

for i in callArr {
    let temp = hash[i]!
    bingArr[temp[0]][temp[1]] = 0
    
    if (isBing(temp[0], temp[1], 0, 1) && isBing(temp[0], temp[1], 0, -1)){
        bingCount += 1
    } //row쪽으로 이동하면서 빙고인지 확인
    if (isBing(temp[0], temp[1], 1, 1) && isBing(temp[0], temp[1], 1, -1)) {
        bingCount += 1
    } //col쪽으로 움직이면서 빙고인지 확인
    if temp[0] == temp[1] {
        bingCount += checkCross(1)
    } //대각선으로 움직이면서 빙고인지 아닌지 확인
    if 4 - temp[0] == temp[1] {
        bingCount += checkCross(-1)
    } //대각선으로 움직이면서 빙고인지 아닌지 확인 
    if bingCount >= 3 {
        print(callArr.firstIndex(of: i)! + 1)
        break
    } //현재 bingCount 3이상이라면 현재 값의 ind번호를 부르며 종료합니다.

}

 

 

전체 코드

import Foundation

func sol() {
    var bingArr:[[Int]] = []
    var callArr:[Int] = []
    for _ in 0..<5 {
        bingArr.append(readLine()!.split(separator: " ").map{Int($0)!})
    }
    for _ in 0..<5 {
        callArr += readLine()!.split(separator: " ").map{Int($0)!}
    }

    func isBing(_ rowVal: Int, _ colVal: Int, _ axis: Int, _ vector: Int) -> Bool { //axis 0이면 row 1이면 col
        if rowVal < 0 || rowVal > 4 || colVal < 0 || colVal > 4 {
            return true
        }
        var tempBing = false
        if bingArr[rowVal][colVal] == 0 {
            if axis == 0 {
                tempBing = isBing(rowVal + 1 * vector, colVal, axis, vector)
            }
            else if axis == 1 {
                tempBing = isBing(rowVal, colVal + 1 * vector, axis, vector)
            }
        }
        return tempBing
    }
    func checkCross(_ pos: Int)-> Int { //1일때는 0 1 2 3 4 
        var count = 0
        if pos >= 0 {
            for i in 0...4 {
                if bingArr[i][i] == 0 {continue}
                else {return count}
            }
            count += 1
        }
        else if pos <= 0 {
            for i in 0...4 {
                if bingArr[4 - i][i] == 0 {continue}
                else {return count}
            }
            count += 1
        }
        return count 
    }

    var bingCount = 0
    var hash: [Int: [Int]] = [:]
    for i in 0 ..< 5 {
        for j in 0 ..< 5 {
            hash[bingArr[i][j]] = [i, j]
        }
    }
    for i in callArr {
        let temp = hash[i]!
        bingArr[temp[0]][temp[1]] = 0
        if (isBing(temp[0], temp[1], 0, 1) && isBing(temp[0], temp[1], 0, -1)){
            bingCount += 1
        }
        if (isBing(temp[0], temp[1], 1, 1) && isBing(temp[0], temp[1], 1, -1)) {
            bingCount += 1
        }
        if temp[0] == temp[1] {
            bingCount += checkCross(1)
        }
        if 4 - temp[0] == temp[1] {
            bingCount += checkCross(-1)
        }
        if bingCount >= 3 {
            print(callArr.firstIndex(of: i)! + 1)
            break
        }
        
    }
}
sol()