백준 16920 확장 게임

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

분류: BFS

---

접근방식

문제 자체도 복잡하긴 한데

문제 설명이 좀 애매해서!!!!! 애를 좀 먹었던 문제였습니다.

Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 

문제를 보면 위와같이 써있는데요, 이렇게 되면 딱 Si 번째 칸만 칠하는 것(성으로 만드는 것)처럼 생각할 수 있는데 그게 아니라 Si번까지 이동하는 중에 있는 칸은 모두 칠해야 합니다. 

반례는 예제 6번에 있는데요,

예제 6번을 살펴보면 처음 플레이어1 이 플레이 하고나면 

["1", "1", "1", "1"]
["1", "1", "1", "1"]
[".", "1", "1", "."]
["1", ".", ".", "2"]

다음과 같이 되고 그 다음에 플레이어2 가 진행하고나면 2는 3이 될 수 밖에 없습니다. 

2년전 쯤에 올라온 질문 등이 있는 것 같은데... 아직 추가 수정이 들어가진 않은 것 같아요,

저는 처음에 Si 번째 칸에만 하도록 접근했었어서, 그 부분도 간략하게 정리하려고는 하는데 우선 이 문제는 Si번으로 이동하는 과정에 있는 칸을 모두 칠해줘야 합니다!

 

---

 

본격적으로 들어가기 전에 약간의 전처리를 해줬는데요,
맵을 Character가 아니라 Int 이차원 배열로 처리해줬습니다.
벽인 "#"은 -1, "." 은 0, 나머지는 player의 수로 해줬어요.

var map = [[Int]](repeating: [Int](repeating: -1, count: nmp[1]), count: nmp[0])

for r in 0..<nmp[0] {
    for (c, value) in readLine()!.enumerated() {
        if value == "." {
            map[r][c] = 0
        } else if let p = Int(String(value)) {
            map[r][c] = p
            queue[p].append((r, c))
            playerCount[p] += 1
        }
    }
}

 

 

이제 시작해보죠! 우선 큰 그림부터 이해해보도록 할게요!!

이 문제는 우선 턴 마다 여러 명의 플레이어가 동시 플레이하는 독특한 방식으로 진행됩니다. 따라서 저는 n명이 이번 턴에 진행해야 할 위치를 담을 큐를 각각 만들어줬어요. 따라서 2차원 배열의 큐가 필요합니다. 

(각 플레이어들이 움직일 수 있는 Si를 담은 배열을 playerMoving으로 만들어줘서 그 개수로 초기화 해줬어요.)

그리고 이 큐가 모두 빌 때까지 반복해주면됩니다. 한 번의 while문은 한 턴이 됩니다.

그리고 각 턴 마다 플레이어가 차례대로 게임을 진행합니다.

var queue = [[Point]](repeating: [Point](), count: playerMoving.count)

while queue.filter({ $0.isEmpty }).count != queue.count {
    // 턴
    for player in 1..<playerMoving.count {
    	// 플레이
    }
}

 

이제 진짜 게임을 해봐야겠죠?

Si까지 움직여야 하기 때문에 이번 턴에 이동해야 할 큐와, 다음 턴에 진행할 큐를 구분해줘야 합니다.

이 부분은 전통적인 BFS 방식입니다,

대신 이번 턴을 담는 큐에는 단순히 위치만 담는 게 아니라 몇 번째 이동 중인지도 같이 기록해줍니다.
(왜냐하면 같은 칸이라도 거쳐갈 수 있기 때문에 한 번 밟았다고 해서 다시 밟지 못하도록 하면 안 됩니다.)

그리고 움직인 횟수가 Si가 되었다면 다음 턴에 넣어주고 아니라면 이번 턴에 다시 넣어줍니다.

그리고 플레이가 끝나면 다음 턴을 큐에 옮겨줍니다.
( nextTurn을 별도로 만들지 않고 queue[player]를 비우고 거기다 바로 채워도 될 거 같아요 :))

var nextTurn = [Point]()
var thisTurn = DoubleStackQueue<(Point, Int)>(queue[player].map { ($0, 0) })

while !thisTurn.isEmpty {
    let (curr, moving) = thisTurn.dequeue()
    
    for d in 0..<4 where 0..<nmp[0] ~= curr.r + dr[d] && 0..<nmp[1] ~= curr.c + dc[d] {
        let next = Point(curr.r + dr[d], curr.c + dc[d])
        guard map[next.r][next.c] == 0 else { continue }
        playerCount[player] += 1
        map[next.r][next.c] = player
        if moving+1 < playerMoving[player] {
            thisTurn.enqueue((next, moving+1))
        } else if moving+1 == playerMoving[player] {
            nextTurn.append(next)
        }
    }
}

queue[player] = nextTurn

 

이번 턴은 칸들을 여러 번 밟을 수 있기 때문에 많이 쌓일 수 있어서 그냥 배열로 하면 시간초과가 나더라구요.
그래서 Queue를 만들어서 처리해줬어요. 

 

여기서 잠깐! 그렇다면 위에 말씀드린 대로 처음에 잘못 접근했던, Si 번째 칸만 밟도록 하려면 어떻게 할까요?

약간의 조작만 해주면 되는데요, map을 칠할 때 턴마다 모두 칠하는 게 아니라 움직인 횟수가 Si가 될 때만 칠해주게 하면 됩니다.

그리고 마지막에 넣어줄 때 이미 칠해진 칸은 의미가 없기 때문에 빈 칸인지만 확인해주면 됩니다 :)

// Si번까지 이동하는 과정을 다 칠하기
playerCount[player] += 1
map[next.r][next.c] = player
if moving+1 < playerMoving[player] {
    thisTurn.enqueue((next, moving+1))
} else if moving+1 == playerMoving[player] {
    nextTurn.append(next)
}

// Si번째만 칠하기
if moving+1 < playerMoving[player] {
    thisTurn.enqueue((next, moving+1))
} else if moving+1 == playerMoving[player], map[next.r][next.c] == 0 {
    nextTurn.append(next)
    map[next.r][next.c] = player
    playerCount[player] += 1
}

 

해결방법

struct DoubleStackQueue<Element> {
    private var inbox: [Element] = []
    private var outbox: [Element] = []
    
    var isEmpty: Bool{
        return inbox.isEmpty && outbox.isEmpty
    }
    
    var count: Int{
        return inbox.count + outbox.count
    }
    
    var front: Element? {
        return outbox.last ?? inbox.first
    }
    
    init() { }
    
    init(_ array: [Element]) {
        self.init()
        self.inbox = array
    }
    
    mutating func enqueue(_ n: Element) {
        inbox.append(n)
    }
    
    mutating func dequeue() -> Element {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox.removeAll()
        }
        return outbox.removeLast()
    }
}

typealias Point = (r: Int, c: Int)
let nmp = readLine()!.split(separator: " ").map { Int(String($0))! }
var playerMoving = [0] + readLine()!.split(separator: " ").map { Int(String($0))! }
var map = [[Int]](repeating: [Int](repeating: -1, count: nmp[1]), count: nmp[0])
var playerCount = [Int](repeating: 0, count: playerMoving.count)
var queue = [[Point]](repeating: [Point](), count: playerMoving.count)

for r in 0..<nmp[0] {
    for (c, value) in readLine()!.enumerated() {
        if value == "." {
            map[r][c] = 0
        } else if let p = Int(String(value)) {
            map[r][c] = p
            queue[p].append((r, c))
            playerCount[p] += 1
        }
    }
}

let dr = [-1, 1, 0, 0]
let dc = [0, 0, -1, 1]

while queue.filter({ $0.isEmpty }).count != queue.count {
    // 턴
    for player in 1..<playerMoving.count {
        var nextTurn = [Point]()
        var thisTurn = DoubleStackQueue<(Point, Int)>(queue[player].map { ($0, 0) })

        while !thisTurn.isEmpty {
            let (curr, moving) = thisTurn.dequeue()
            
            for d in 0..<4 where 0..<nmp[0] ~= curr.r + dr[d] && 0..<nmp[1] ~= curr.c + dc[d] {
                let next = Point(curr.r + dr[d], curr.c + dc[d])
                guard map[next.r][next.c] == 0 else { continue }
                playerCount[player] += 1
                map[next.r][next.c] = player
                if moving+1 < playerMoving[player] {
                    thisTurn.enqueue((next, moving+1))
                } else if moving+1 == playerMoving[player] {
                    nextTurn.append(next)
                }
            }
        }
        queue[player] = nextTurn
    }
}

print(playerCount.dropFirst().map({ String($0) }).joined(separator: " "))

 

배운점

쉽지 않았다... ~_~..