[BOJ] 22251 빌런 호석 (Swift)

문제 링크 

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

 

문제 이름처럼 정말 빌런같았던 문제,, 질문 게시판을 참고해서 풀었다. 

 

문제 접근

반전시켜야 하는 LED 수 구하기 

 

가장 첫 번째로 위 사진처럼 7세그먼트로 표현된 숫자를 다른 숫자로 바꾸기 위해 몇 개의 LED를 반전시켜야하는지 알아야 한다. 

정말 처음 접근으로는 각 숫자 별로 다른 숫자로 바꾸기 위해 반전시켜야 하는 LED 수를 하나하나 써서 찾으려고 했다. 근데 코드로도 구할 수 있을 것 같아서 방향을 틀었다. 

노가다 ..

 

숫자 별로 불이 들어오는 표시등의 위치를 숫자로 표현한 후 차집합을 이용해서 반전시킬 LED 수를 구하자

질문 게시판에서 얻은 아주 좋은 아이디어이다. 

 

LED의 위치에 따라 숫자를 아래와 같이 부여했다. 

그렇다면 0부터 9까지의 수를 이렇게 표현할 수 있다. 

let number: [Set<Int>] = [
    [0,1,3,4,5,6], 	 // 0
    [3,6], 			 // 1
    [0,2,3,4,5], 	 // 2
    [0,2,3,5,6], 	 // 3
    [1,2,3,6], 		 // 4
    [0,1,2,5,6], 	 // 5
    [0,1,2,4,5,6], 	 // 6
    [0,3,6], 		 // 7
    [0,1,2,3,4,5,6], // 8
    [0,1,2,3,5,6]	 // 9
]

 

 

두 집합이 있을 때 우리가 구해야 하는 범위는 아래 그림에서 노란색으로 칠한 부분과 같다. 해당 부분이 한 숫자에서 다른 숫자로 바꾸기 위해 반전시켜야 하는 LED의 수가 된다. 

 

해당 부분은 차집합을 이용해서 구했다. 

number[n1].subtracting(number[n2]).count + number[n2].subtracting(number[n1]).count

 

하지만 구할 필요가 있을 때마다 위 코드가 실행된다면 시간이 너무 오래 걸릴 수 있기 때문에 한 번 구하면 값을 저장해줬다. (실제로 그렇게 풀었다가 시간초과가 났다)

 

배열 `d`에 저장된 값이 있다면 바로 return을 하고, 값이 없다면 계산 후 배열 `d`에 저장했다. 

var d: [[Int]] = Array(repeating: Array(repeating: -1, count: 10), count: 10)
for i in 0..<d.count {
    d[i][i] = 0
}

// 두 집합의 다른 요소의 개수를 구하는 함수
func difference(_ n1: Int, _ n2: Int) -> Int {
    if d[n1][n2] > -1 {
        return d[n1][n2]
    }
    
    let count = number[n1].subtracting(number[n2]).count + number[n2].subtracting(number[n1]).count
    d[n1][n2] = count
    d[n2][n1] = count
    
    return count
}

 

재귀로 구하기 

바꾼 층수의 범위도 고려해야 하고 반전시킬 수 있는 최대 LED 수도 고려해야 하니 dfs 탐색을 하듯이 재귀로 풀었다. 

 

함수의 매개변수로는

`idx`: 현재 바꾸려는 숫자의 자리수, `count`: 반전시킨 LED 수, `str`: 현재 탐색 중인 층 

이렇게 3개이다. 

 

현재 바꿀 숫자를 기준으로 다른 어떤 숫자로 바꿀 수 있는지 확인하는 방식이다. 

 

[고려해야할 조건]

1. LED는 1~p개까지만 반전 가능

2. 바꾼 층수는 1 이상, n 이하 

 

위 조건을 모두 만족했을 때, 답이 되는 `answer`의 값을 1 증가시키고 다음 자리수를 탐색하기 위해 함수를 다시 호출한다. 

주의해야 할 점은 `answer` 값을 업데이트하는 것은 `k`개의 자리수에 맞게 모두 탐색을 완료했을 때만 해야 한다. 즉 현재 위치가 마지막 자리일 때만 업데이트를 해야한다. 

 

func f(_ idx: Int, _ count: Int, _ str: String) {
    if idx >= k { return }
        
    // 현재 바꿀 숫자
    let cur = Int(String(xArr[idx]))!
    
    for i in 0..<number.count {
        // cur에서 i로 바꾸기 위해 반전시켜야 할 LED 수
        let c = difference(cur, i)
        
        // (현재 반전시킨 count) + c 가 p 이하여야 함
        if count + c > p { continue }
        
        let storedStr = str+String(i)
        
        // 바꾼 층수가 n보다 낮아야 함
        if Int(String(nArr[0...idx]))! < Int(storedStr)! { continue }
        
        // 마지막 자리수일 때, 1. 바꾼 층이 0이면 안됨 2. 바꾼 층이 처음과 같으면 안됨
        if idx == k-1 && (Int(storedStr)! == 0 || storedStr == String(xArr)) { continue }
        
        // 마지막 자리수일 때, 모든 조건을 통과하였으므로 +1
        if idx == k-1 {
            answer += 1
        }
        
        f(idx+1, count+c, storedStr)
    }
}

 

전체 코드

전체 코드는 다음과 같다. 

import Foundation

let input = readLine()!.split(separator: " ").map{Int($0)!}
let (n,k,p,x) = (String(input[0]),input[1],input[2],String(input[3]))

let number: [Set<Int>] = [[0,1,3,4,5,6], [3,6], [0,2,3,4,5], [0,2,3,5,6], [1,2,3,6], [0,1,2,5,6], [0,1,2,4,5,6], [0,3,6], [0,1,2,3,4,5,6], [0,1,2,3,5,6]]

let nArr = Array(String(repeating: "0", count: k-n.count) + n)
let xArr = Array(String(repeating: "0", count: k-x.count) + x)

var answer = 0

var d: [[Int]] = Array(repeating: Array(repeating: -1, count: 10), count: 10)
for i in 0..<d.count {
    d[i][i] = 0
}

// 두 집합의 다른 요소의 개수를 구하는 함수
func difference(_ n1: Int, _ n2: Int) -> Int {
    if d[n1][n2] > -1 {
        return d[n1][n2]
    }
    
    let count = number[n1].subtracting(number[n2]).count + number[n2].subtracting(number[n1]).count
    d[n1][n2] = count
    d[n2][n1] = count
    
    return count
}

func f(_ idx: Int, _ count: Int, _ str: String) {
    if idx >= k { return }
        
    // 현재 바꿀 숫자
    let cur = Int(String(xArr[idx]))!
    
    for i in 0..<number.count {
        // cur에서 i로 바꾸기 위해 반전시켜야 할 LED 수
        let c = difference(cur, i)
        
        // (현재 반전시킨 count) + c 가 p 이하여야 함
        if count + c > p { continue }
        
        let storedStr = str+String(i)
        
        // 바꾼 층수가 n보다 낮아야 함
        if Int(String(nArr[0...idx]))! < Int(storedStr)! { continue }
        
        // 마지막 자리수일 때, 1. 바꾼 층이 0이면 안됨 2. 바꾼 층이 처음과 같으면 안됨
        if idx == k-1 && (Int(storedStr)! == 0 || storedStr == String(xArr)) { continue }
        
        // 마지막 자리수 일때, 모든 조건을 통과하였으므로 +1
        if idx == k-1 {
            answer += 1
        }
        
        f(idx+1, count+c, storedStr)
    }
}

f(0,0,"")
print(answer)

 

 

정말 ... 풀기 힘들었다..  처음에는 반복문을 돌려서 풀려고 했다가 p값을 어떻게 처리해야할지 방법이 생각나지 않았다. .. 휴 . .

 

요새 조건을 처리할 때 continue 또는 return으로 조건에 맞지 않는 것을 하나하나 걸러내는 방법을 자주 쓰고있다. 고려해야할 사항이 많을 때는 개인적으로 이렇게 하나씩 걸러내는 방법이 좋은 것 같다. 

문제가 어려울수록 주석을 달아가며 풀고있기 때문에 그런 것 같기도 하다 ㅎㅎ

 

후 빌런아 안녕!