[Swift][구현] 백준 15662 (톱니바퀴(2))

요구능력

구현, 큐

 

문제풀이

변경되기 이전의 톱니바퀴끼리 비교를 해야하기 때문에 변경되기 이전의 톱니바퀴들을 미리 저장해둔다.(beforeLoc)

처음에 재귀로 접근했다가 이상하게 빠져버려서 시간을 많이 낭비했다가 포기하고 큐로 풀게되었다.

큐로 접근해서 방문처리를 해주면 똑같은 톱니바퀴를 돌지않고, 딱 돌아야하는 톱니바퀴만 돌 수 있다.

방문처리를 해주는 이유는 예를 들어 1번부터 출발해서 4번까지 가는데 중간에 2번에서 1번과 극이 다르다면 조건을 충족하기 때문에 1번을 또 돌릴 수도 있는 경우를 방지하기 위해서이다.

 

재귀로도 풀리긴 하지만, 큐로 푸는것이 효율적인 것 같다.

후기

변경되기 이전의 값을 쓰는 문제에서는 변경되기 이전의 값을 먼저 저장해놓자!

 

코드

import Foundation
let t = Int(String(readLine()!))!
var arr = [[Int]]()
for _ in 0..<t{
    arr.append(readLine()!.map{Int(String($0))!})
}

let k = Int(String(readLine()!))!
for _ in 0..<k{
    let nr = readLine()!.split(separator: " ").map{Int(String($0))!}
    let n = nr[0] - 1 //인덱스 맞추기위해 -1
    let r = nr[1]
    var queue = [(Int, Int)]()//몇번째 톱니바퀴인지, 방향
    var beforeLoc = [(Int, Int)]() //톱니바퀴가 돌기전의 상태를 저장해놔야함.
    var visited = Array(repeating: false, count: t)
    for i in 0..<t{
        beforeLoc.append((arr[i][2], arr[i][6]))
    }
    queue.append((n, r))
    visited[n] = true
    while !queue.isEmpty{
        let (curN, curR) = queue.removeFirst()
        rotate(curN, curR)
        if curN == 0{
            if rightDistinction(beforeLoc, curN){
                if !visited[curN + 1]{
                    visited[curN + 1] = true
                    queue.append((curN + 1, curR * -1))
                }
            }
        }else if curN == t-1{
            if leftDistinction(beforeLoc, curN){
                if !visited[curN - 1]{
                    visited[curN - 1] = true
                    queue.append((curN - 1, curR * -1))
                }
            }
        }else{
            if rightDistinction(beforeLoc, curN){
                if !visited[curN + 1]{
                    visited[curN + 1] = true
                    queue.append((curN + 1, curR * -1))
                }
            }
            if leftDistinction(beforeLoc, curN){
                if !visited[curN - 1]{
                    visited[curN - 1] = true
                    queue.append((curN - 1, curR * -1))
                }
            }
        }
    }
    
}
func rotate(_ curN: Int, _ curR: Int){
    var temp = Array(repeating: 0, count: 8)
    var idx = 0
    for _ in 0..<8{
        let inIdx: Int = {
            if idx + curR < 0{
                return 7
            }else if idx + curR > 7{
                return 0
            }else {
                return idx + curR
            }
        }()
        temp[inIdx] = arr[curN][idx]
        idx += 1
    }
    arr[curN] = temp
}

func leftDistinction(_ loc: [(Int, Int)], _ curN: Int) -> Bool{//극이 달라서 반대방향으로 회전해야되면 true
    if loc[curN].1 != loc[curN - 1].0{
        return true
    }else{
        return false
    }
}

func rightDistinction(_ loc: [(Int, Int)], _ curN: Int) -> Bool{//극이 달라서 반대방향으로 회전해야되면 true
    if loc[curN].0 != loc[curN + 1].1{
        return true
    }else{
        return false
    }
}
var count = 0
for i in arr{
    if i[0] == 1{
        count += 1
    }
}
print(count)