백준 14891 톱니바퀴

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

분류: 시뮬레이션

---

접근방식 

주어진 규칙에 따라 톱니바퀴를 회전시킨 후 결과를 계산하는 문제였습니다.
톱니바퀴를 회전시킨다는 건 톱니바퀴를 바라보는 관점만 바꿔주면 됩니다. 즉 가리키는 인덱스만 바꿔주면 회전과 같은 효과를 얻을 수 있겠죠.
시계방향으로 톱니바퀴의 극이 주어지는데 12시 방향을 0으로 생각하면, 양쪽에 맞물려서 확인해야 하는 지점은, 톱니의 왼쪽은 6, 오른쪽은 2가 됩니다. 

따라서
시계방향으로 회전시키려면 톱니의 왼쪽 오른쪽을 -1 해주면되고
반시계방향으로 회전시키려면 톱니의 왼쪽 오른쪽을 +1 해주면 됩니다.

회전이니까 나머지 연산을 잘 사용해주면 손쉽게 구현해줄 수 있습니다.

if dir == 1 {
  // 반시계
    pole[saw].left = (pole[saw].left + 7) % 8
    pole[saw].right = (pole[saw].right + 7) % 8
} else {
  // 시계
    pole[saw].left = (pole[saw].left + 1) % 8
    pole[saw].right = (pole[saw].right + 1) % 8
}

그럼 확인할 건

현재 톱니의 오른쪽과 오른쪽 톱니의 왼쪽, 
현재 톱니의 왼쪽과 왼쪽 톱니의 오른쪽이

서로 반대 극인지 확인하면 됩니다.

 

이제 양쪽에 톱니가 있는지, 반대인지 확인해서 재귀적으로 반복해주면 됩니다.
한 가지 주의해야 할 점은 회전시키기 전에 극이 반대인지 확인해서 재귀호출해주고 끝나면 마지막에 회전을 시켜줘야 합니다 :)

 

해결방법

var sawTooth = [[Int]]()
for _ in 0..<4 {
    sawTooth.append(Array(readLine()!).map({ Int(String($0))! }))
}

var pole = [(left: Int, right: Int)](repeating: (6, 2), count: 4)
let movedInit = [Bool](repeating: false, count: 4)
var moved = movedInit

func move(_ saw: Int, _ dir: Int) {
    moved[saw] = true
    let (left, right) = (pole[saw].left, pole[saw].right)
    if saw+1 < 4, !moved[saw+1] {
        let (aroundLeft, _) = pole[saw+1]
        if sawTooth[saw][right] != sawTooth[saw+1][aroundLeft] {
            move(saw+1, dir*(-1))
        }
    }
    if saw-1 >= 0, !moved[saw-1] {
        let (_, aroundRight) = pole[saw-1]
        if sawTooth[saw][left] != sawTooth[saw-1][aroundRight] {
            move(saw-1, dir*(-1))
        }
    }
    
    if dir == 1 {
        pole[saw].left = (pole[saw].left + 7) % 8
        pole[saw].right = (pole[saw].right + 7) % 8
    } else {
        pole[saw].left = (pole[saw].left + 1) % 8
        pole[saw].right = (pole[saw].right + 1) % 8
    }
}

let k = Int(readLine()!)!
for _ in 0..<k {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let (saw, dir) = (input[0]-1, input[1])
    moved = movedInit
    move(saw, dir)
}

var score = 0
for i in (0..<4) {
    let top = (pole[i].left + 2) % 8
    if sawTooth[i][top] == 1 {
        score += 1<<(i)
    }
}
print(score)

 

배운점

뭐에 씌였는지... 반시계로 돌릴 때 max(0, pole -1) 이런 식으로 해서 한참을 날렸다...