글 읽기 - 질문글 반례를 모두 넣어서 통과되나 틀리다고 나오네요.

testtest4 3년 전 0

1 1

등 뭐 질문글에 있는 테스트케이스를 돌려봐도 제대로 나오는것 같은데 틀린 이유를 모르겠네요...

브루트포스이니 dfs를 썼습니다.

cctv의 위치와 값을 struct를 이용해서 저장하고, cctv에 배열로 저장하였습니다.

dfs로 cctv의 종류에 따라 구분하였고, 방향을 돌려서 dfs를 구현했는데 왜 틀릴까요..?

고수님들의 도움이 필요합니다!!

func solution15683() {
    let NM = readLine()!.split(separator: " ").map { Int($0)! }
    var office = [[Int]]()
    
    struct Cctv {
        var value: Int
        var x: Int
        var y: Int
    }
    
    var cctv = [Cctv]()
    var answer = 9999999999

    let dx = [0,0,1,-1]
    let dy = [1,-1,0,0]
    
    let ddx = [1,0,-1,0,1,0]
    let ddy = [0,1,0,-1,0,1]
    
    // 사무실의 범위를 벗어나는지 조사
    func checkRange(x: Int, y: Int) -> Bool {
        return x >= 0 && y >= 0 && x < NM[0] && y < NM[1]
    }
    
    // 감시카메라의 위치와 방향에 맞는 쪽으로 7을 그린다. 벽이면 그만두고, 1에서 5면 pass, 아닌 경우는 7을 넣어준다
    func markRange(x: Int, y: Int, office: inout [[Int]], mx: Int, my: Int){
        //여기서는 office에 방향을 그린다.
        
        for i in 1 ..< 8 {
            let cx = x + mx*i
            let cy = y + my*i
            
            if checkRange(x: cx, y: cy) {
                if office[cx][cy] == 6 {
                    //벽이니 stop
                    break
                } else if 1 <= office[cx][cy] && office[cx][cy] <= 5 {
                    continue
                } else {
                    office[cx][cy] = 7
                }
            } else {
                break
            }
        }
        
        //return office
    }
    
    // cctv의 개수에 도달하면 dfs를 멈춘다
    func dfs(depth: Int, myOffice: [[Int]] ) {
        
        // 만약 모든 cctv를 다 돌았을 경우 return
        if depth >= cctv.count {
            var sum = 0
            
            myOffice.forEach { room in
                sum += room.filter { $0 == 0}.count
            }
            
            answer = min(answer, sum)
            return
        }
        
        var Office = myOffice
        
        if cctv[depth].value == 1 {
            // 4방향으로 검사
            for i in 0 ..< 4 {
                Office = myOffice
                markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: dx[i], my: dy[i])
                dfs(depth: depth + 1, myOffice: Office)
            }
            
        } else if cctv[depth].value == 2 {
            // 두방향으로 검사
            for i in stride(from: 0, to: 2, by: 2) {
                Office = myOffice
                markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: dx[i], my: dy[i])
                markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: dx[i+1], my: dy[i+1])
                dfs(depth: depth + 1, myOffice: Office)
            }
            
        } else if cctv[depth].value == 3 {
            // 다른 두방향으로 검사
            for i in 0 ..< 4 {
                Office = myOffice
                markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: ddx[i], my: ddy[i])
                markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: ddx[i + 1], my: ddy[i + 1])
                dfs(depth: depth + 1, myOffice: Office)
            }
            
        } else if cctv[depth].value == 4 {
            for i in 0 ..< 4 {
                Office = myOffice
                markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: ddx[i], my: ddy[i])
                markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: ddx[i + 1], my: ddy[i + 1])
                markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: ddx[i + 2], my: ddy[i + 2])
                dfs(depth: depth + 1, myOffice: Office)
            }
            
        } else if cctv[depth].value == 5 {
            markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: 0, my: 1)
            markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: 0, my: -1)
            markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: 1, my: 0)
            markRange(x: cctv[depth].x, y: cctv[depth].y, office: &Office, mx: -1, my: 0)
            dfs(depth: depth + 1, myOffice: Office)
        }
        
    }
    
    for i in 0 ..< NM[0] {
        let temp = readLine()!.split(separator: " ").map { Int($0)! }
        for tempIndex in 0 ..< temp.count {
            if temp[tempIndex] != 0 && temp[tempIndex] != 6 {
                
                var tempCCTV = Cctv(value: temp[tempIndex], x: i, y: tempIndex)
                cctv.append(tempCCTV)
            }
        }
        office.append(temp)
    }
    
    //depth는 cctv 배열의 위치, 0부터 시작
    dfs(depth: 0, myOffice: office)
    
    print(answer)
}

func solution15683()

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

질문글 반례를 모두 넣어서 통과되나 틀리다고 나오네요.

testtest4 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말