백준 17135 캐슬디펜스

출처: www.acmicpc.net/problem/17135

분류: 시뮬레이션

---

접근방식

구현도 구현인데 생각을 좀 잘못해서 몇 번의 시행착오를 겪었습니다. 문제를 잘 읽지 않으면 틀릴 수 있는 주의해야 할 점들이 몇 가지 있었던 문제 같습니다.

저는 문제를 보고 크게 3가지의 구현 단계로 나눠야겠다고 생각했습니다.

1. 궁수 3명 뽑기

2. 현 위치에서 제거 가능한 적 찾기

3. 궁수 전진

각 부분이 잘 구현되면 흐름에 따라 답을 찾는 건 어렵지 않게 할 수 있습니다. 저는 우선 주어진 맵 밑에 궁수가 배치될 행 (n행) 을 하나 추가했는데요,

여기에 궁수를 두고 나머지 적을 모두 밑으로 내리는 건 에너지 소모가 굉장히 큰 일이라서,
저는 여기서부터 출발해 궁수가 한 칸씩 위로 올라가면서 적을 죽이는 방식으로 생각했습니다.
이미 지나온 칸은 신경쓸 필요가 없기 때문에 현재 궁수의 행만 기록해뒀다가 행을 n..<0 까지 루프를 돌면서 처리해줬어요.

 

흐름이 잡히셨다면 구현을 하나씩 살펴볼까요?

 

1. 궁수 3명 뽑기

이건 조합을 통해서 구해줄 수 있습니다. 시뮬레이션에서 순열 조합은 거의 밥 먹을 때 젓가락질 수준으로 해야하는 것 같아요...

궁수를 뽑으면서 3명이 되면 게임을 시작합니다.

func addArcher(_ curr: Int) {
    guard archers.count < 3 else {
        let attackPoint = play()
        if maxPoint < attackPoint {
            maxPoint = attackPoint
        }
        return
    }
    
    guard curr < nmd[1] else { return }
    archers.append(curr)
    addArcher(curr+1)
    archers.removeLast()
    addArcher(curr+1)
}

 

2. 현 위치에서 제거 가능한 적 찾기

궁수가 배치되었다면, 각 궁수의 위치에서 제거 가능한 적들을 찾아줘야 합니다.

저는 여기서 좀 실수를 많이 했는데요, 2가지에 유의하셔야 합니다.

2-1. 가장 가까운 적부터 처리하고 여러 개라면 가장 왼쪽부터 처리한다.

처음에 거리에 상관없이 왼쪽부터 가능한 적을 싹 구했다가 틀렸습니다. ㅠㅠ 거리가 우선이에요!

거리 1은 바로 앞이니 먼저 처리해줬고, 아래와 같이 거리 2부터 가능한 적들을 쭉쭉 찾아줬습니다.

for d in 2...dist {
    (archer.c - (d-1)...archer.c + (d-1)).forEach { col in
        let colDist = abs(archer.c - col)
        let row = archer.r - (d-colDist)
        if isInRange((row, col)) {
            validPoints.append((row, col))
        }
    }
}

 

2-2. 궁수는 같은 적을 공격할 수 있다.

저는 적을 공격하면 맵의 1을 0으로 바꾸는 방식으로 처리를 해줬는데요, 이걸 각 궁수마다 바로 처리해버리면

만약 위 우선순위에 따라 두 궁수가 같은 적을 공격해야 하는 경우에는 같은 적을 공격하지 못하고 더 똑똑하게(?) 다음 적을 공격해서 문제 상황과 맞지 않게 됩니다. 따라서 저는 우선 궁수 3명이 공격한 지점을 모아뒀다가 한 번에 처리해주는 방식으로 처리했어요.

for archer in archers {
    for point in validRange(at: (attackRow, archer)) {
        if playingMap[point.r][point.c] == 1 {
        	// 여기서 바로바로 맵을 0으로 바꾸고 attackPoint를 증가시키면 안 됨!
            attacked.append(point)
            break
        }
    }
}
while !attacked.isEmpty {
    let point = attacked.popLast()!
    if playingMap[point.r][point.c] == 1 {
        playingMap[point.r][point.c] = 0
        attackPoint += 1
    }
}

 

3. 궁수 전진

앞서 말씀드린 대로 궁수 전진은 그냥 궁수의 행만 기록해뒀다가 n..<0 까지 반복 해줬습니다.

func play() -> Int {
  ...
  attackRow = n // n-1 행까지 주어진 맵 밑에 행을 하나 추가해뒀음. 
  while attackRow > 0 {
      // attackPoint 체크
  }
  
  return attackPoint
}

 

 

해결방법

// 17135 캐슬디펜스

typealias Point = (r: Int, c: Int)

// 행 열 거리
let nmd = readLine()!.split(separator: " ").map { Int(String($0))! }
var map = [[Int]]()
for _ in 0..<nmd[0] {
    map.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

map.append([Int](repeating: 0, count: nmd[1]))
var maxPoint = 0

// 궁수 3명 배치

var archers = [Int]()
func addArcher(_ curr: Int) {
    guard archers.count < 3 else {
        let attackPoint = play()
        if maxPoint < attackPoint {
            maxPoint = attackPoint
        }
        return
    }
    
    guard curr < nmd[1] else { return }
    archers.append(curr)
    addArcher(curr+1)
    archers.removeLast()
    addArcher(curr+1)
}

func play() -> Int {
    var playingMap = map
    var attackPoint = 0
    var attackRow = nmd[0]
    var attacked = [Point]()
    
    while attackRow > 0 {
        for archer in archers {
            for point in validRange(at: (attackRow, archer)) {
                if playingMap[point.r][point.c] == 1 {
                    attacked.append(point)
                    break
                }
            }
        }
        while !attacked.isEmpty {
            let point = attacked.popLast()!
            if playingMap[point.r][point.c] == 1 {
                playingMap[point.r][point.c] = 0
                attackPoint += 1
            }
        }
        attackRow -= 1
    }
    
    return attackPoint
}

func isInRange(_ p: Point) -> Bool {
    return 0..<nmd[0] ~= p.r && 0..<nmd[1] ~= p.c
}

func validRange(at archer: Point) -> [Point] {
    guard nmd[2] > 1 else { return [(archer.r-1, archer.c)] }
    var validPoints = [(archer.r-1, archer.c)]
    let dist = nmd[2]
    
    for d in 2...dist {
        (archer.c - (d-1)...archer.c + (d-1)).forEach { col in
            let colDist = abs(archer.c - col)
            let row = archer.r - (d-colDist)
            if isInRange((row, col)) {
                validPoints.append((row, col))
            }
        }
    }
    
    return validPoints
}

addArcher(0)
print(maxPoint)

 

배운점

예전에 한 번 풀어보려고 시도했다가 못해먹겠다~ 하고 넘어갔던 문젠데 이번엔 어렵지 않게 풀 수 있었다. (시행착오를 좀 겪긴했지만..)

전보단 조금 발전했나보다. 화이팅!!