백준 1941 소문난 칠공주

출처: https://www.acmicpc.net/problem/1941

분류: brute force

---

접근방식

처음엔 그냥 bfs, dfs로 풀 수 있겠거니 했으나.... 점점 어라? 어라..? 어라....????!! 하며 쉽지 않았던 문제였습니다.

중복을 어떻게 줄여줘야할지 도통 감이 오질 않더라구요..

결국은 다음와 같은 과정으로 해결했습니다.

1. 각 칸을 0~24로 두고, 0~24 중 7개를 선택하는 조합을 구한다. (약 48만개)

2. 조합에서 S가 4명 이상인지 확인한다

3. 조합이 모두 인접해있는지 확인한다.

1, 2번까지는 어렵지 않게 구할 수 있을 거 같은데 3번이 살짝 까다롭네요.

3번은 만든 조합의 0번부터 시작해 인접한 수가 조합안에 있는지 확인하고 queue에 담아주면서 탐색하는 식으로 해결했습니다.

visit 배열을 두고 각 원소를 한 번씩만 탐색해야하는데, 결과적으로 7번을 모두 탐색해서 visit이 모두 true가 되어야 참입니다.

저는 queue를 제거하지 않고 queue 인덱스를 따로 둬서 7까지 갔는지 확인하는 식으로 마무리해줬습니다 :)

func isAdjacent(_ array: [Int]) -> Bool {
    var queue = [array[0]]
    var visit = [Bool](repeating: false, count: 7)
    visit[0] = true
    var qIdx = 0
    while qIdx < queue.count {
        let (r, c) = (queue[qIdx]/5, queue[qIdx]%5)
        qIdx += 1
        for d in delta {
            let nr = r + d[0], nc = c + d[1]
            guard nr >= 0, nr < 5, nc >= 0, nc < 5 else { continue }
            for idx in 0..<7 where !visit[idx] {
                if array[idx] == nr*5 + nc {
                    queue.append(array[idx])
                    visit[idx] = true
                    break
                }
            }
        }
    }
    return queue.count == 7
}

 

 

해결방법

var map = [[Character]]()
for _ in 0..<5 {
    map.append(Array(readLine()!))
}

func isS(_ idx: Int) -> Bool {
    let r = (idx/5), c = (idx%5)
    return map[r][c] == "S"
}

let delta = [[-1, 0], [1, 0], [0, -1], [0, 1]]
func isAdjacent(_ array: [Int]) -> Bool {
    var queue = [array[0]]
    var visit = [Bool](repeating: false, count: 7)
    visit[0] = true
    var qIdx = 0
    while qIdx < queue.count {
        let (r, c) = (queue[qIdx]/5, queue[qIdx]%5)
        qIdx += 1
        for d in delta {
            let nr = r + d[0], nc = c + d[1]
            guard nr >= 0, nr < 5, nc >= 0, nc < 5 else { continue }
            for idx in 0..<7 where !visit[idx] {
                if array[idx] == nr*5 + nc {
                    queue.append(array[idx])
                    visit[idx] = true
                    break
                }
            }
        }
    }
    return queue.count == 7
}

var resultCase = 0
var temp = [Int]()
var sCount = 0
func combi(_ idx: Int) {
    guard temp.count < 7 else {
        if sCount >= 4, isAdjacent(temp) {
            resultCase += 1
        }
        return
    }
    guard idx < 25 else { return }
    temp.append(idx)
    let s = isS(idx) ? 1 : 0
    sCount += s
    combi(idx+1)
    sCount -= s
    temp.removeLast()
    combi(idx+1)
}
combi(0)

print(resultCase)

 

배운점

연습만이 살길 🔥