백준의 마법사 상어 시리즈 중 파이어볼, 토네이도, 파이어스톰, 비바라기 문제입니다.
단순 구현 문제라 코드가 길어 전체 코드는 링크로 첨부합니다.
모든 코드는 https://github.com/jeongju9216/Algorithm/tree/main/Swift 에서 볼 수 있습니다.
Swift 코드가 올라와 있는게 많이 없어서 자세한 풀이보다는 개인 복습 겸 올렸습니다.
마법사 상어와 파이어볼 (BOJ 20056)
풀이 코드 : https://github.com/jeongju9216/Algorithm/blob/main/Swift/BOJ/20000/20056.swift
파이어볼을 범위 밖으로도 이동 시키는 작업이 포인트인 문제입니다.
- 질량이 0인 파이어볼은 사라진다는 점
- 파이어볼은 4방향으로 퍼지는게 아니라 그 자리에서 4개로 분리된다는 점
- 0, 2, 4, 6인 경우는 모두 홀수이거나 모두 짝수라는 점
위 세 가지만 주의하면 나머지는 구현으로 풀 수 있습니다.
파이어볼을 이동시키는 코드만 살펴보겠습니다.
원형 큐처럼 범위를 벗어났을 때 반대쪽으로 이어서 움직이는게 중요합니다.
let dx = [-1, -1, 0, 1, 1, 1, 0, -1]
let dy = [0, 1, 1, 1, 0, -1, -1 ,-1]먼저 문제 정의대로 방향 벡터를 선언합니다.
그리고 k번 만큼 파이어볼들을 이동시켜야 합니다.
func move(_ fireballs: [FireBall], _ tmpMap: inout [[[FireBall]]]) {
for fireball in fireballs {
let moving = fireball.s % n
let nx = (fireball.r + moving * dx[fireball.d] + n) % n
let ny = (fireball.c + moving * dy[fireball.d] + n) % n
let new = FireBall(r: nx, c: ny, m: fireball.m, s: fireball.s, d: fireball.d)
tmpMap[nx][ny].append(new)
}
}위 이동 코드에서 3 ~ 5줄이 중요합니다.
1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있기 때문에 이동 거리를 맵 크기인 n으로 나눠서 실제로 이동하는 칸 수를 구합니다. 위에서 선언한 방향 벡터를 이용해 이동할 방향으로 이동시키면 됩니다.
마법사 상어와 토네이도 (BOJ 20057)
풀이 코드 : https://github.com/jeongju9216/Algorithm/blob/main/Swift/BOJ/20000/20057.swift
토네이도를 기준으로 문제에 나와 있는 %만큼 이동시키는 문제입니다.
토네이도의 방향 전환은 규칙이 있습니다.
서풍 -> 남풍 -> 동풍 -> 북풍으로 이동하기 때문에
동서남북 방향 벡터를 선언하고
//동서남북
let dx = [0, 0, 1, -1], dy = [1, -1, 0, 0]func changeDirection(_ current: Int) -> Int {
switch current {
case 0: return 3
case 1: return 2
case 2: return 0
case 3: return 1
default: return -1
}
}다음 방향을 구하는 메서드를 정의했습니다.
이제 모래를 움직이는 코드를 살펴봅시다.
토네이도를 기준으로 %와 a가 위치해 있는 좌표를 선언합니다.
//1 1 7 7 10 10 2 2 5 비율 매핑
//토네이도 중심 기준으로 비율이 들어있는 좌표
let xdx = [
[-1, 1, -1, 1, -1, 1, -2, 2, 0, 0],
[-1, 1, -1, 1, -1, 1, -2, 2, 0, 0],
[0, 0, 1, 1, 2, 2, 1, 1, 3, 2],
[0, 0, -1, -1, -2, -2, -1, -1, -3, -2]
]
let ydy = [
[0, 0, 1, 1, 2, 2, 1, 1, 3, 2],
[0, 0, -1, -1, -2, -2, -1, -1, -3, -2],
[-1, 1, -1, 1, -1, 1, -2, 2, 0, 0],
[-1, 1, -1, 1, -1, 1, -2, 2, 0, 0]
]
let percent = [1, 1, 7, 7, 10, 10, 2, 2, 5]위 좌표를 이용해서 토네이도 위치에 따라 모래를 움직입니다.
let tmp = sand
//비율 좌표 9개 확인
for i in 0..<9 {
let nx = x + xdx[d][i]
let ny = y + ydy[d][i]
let per = percent[i]
let plus = (tmp * per) / 100
if (1...n) ~= nx, (1...n) ~= ny {
//범위 안이면 모래 합치기
map[nx][ny] += plus
} else {
//범위를 벗어나면 결과에 더함
result += plus
}
sand -= plus
}이때 a는 모든 모래를 이동시켜야 하므로 따로 처리해 주었습니다.
//a 위치 계산 -> 모든 모래 이동
let nx = x + xdx[d][9]
let ny = y + ydy[d][9]
if (1...n) ~= nx, (1...n) ~= ny {
map[nx][ny] += sand
} else {
result += sand
}
map[xx][yy] = 0
마법사 상어와 파이어스톰 (BOJ 20058)
풀이 코드 : https://github.com/jeongju9216/Algorithm/blob/main/Swift/BOJ/20000/20058.swift
맵을 나누고 배열을 회전시키는게 포인트인 문제입니다.
맵을 나눠서 회전시키는 코드를 보겠습니다.
func turnMap(_ l: Int) {
let jump = Int(pow(2.0, Double(l)))
for i in stride(from: 0, to: size, by: jump) {
for j in stride(from: 0, to: size, by: jump) {
let tmpMap = map[i..<i+jump].map { Array($0[j..<j+jump]) }
for x in 0..<tmpMap.count {
for y in 0..<tmpMap[0].count {
map[i+x][j+y] = tmpMap[tmpMap.count-y-1][x]
}
}
}
}
}문제 정의대로 jump는 2의 L제곱입니다.
stride를 이용해서 jump씩 뛰면서 배열을 회전 시키고, 다음 범위로 이동하는 코드입니다.
아래는 얼음을 녹이는 코드입니다.
func meltingIce() {
var visited: [[Int]] = Array(repeating: Array(repeating: 0, count: size), count: size)
for i in 0..<size {
for j in 0..<size {
guard map[i][j] > 0 else {
continue
}
for k in 0..<4 {
let nx = i + dx[k]
let ny = j + dy[k]
guard (0..<size) ~= nx, (0..<size) ~= ny else {
continue
}
if map[nx][ny] > 0 {
visited[i][j] += 1
}
}
}
}
for i in 0..<size {
for j in 0..<size {
if map[i][j] > 0 && visited[i][j] < 3 {
map[i][j] -= 1
}
}
}
}map[i][j]에 따라 4방향만 살펴보면 되기 때문에 BFS처럼 큐를 사용하진 않았습니다.
얼음이 남아있는 곳을 기준으로 4방향을 보고 인접한 얼음이 아닌 곳의 개수를 구합니다.
3개 이상이라면 얼음을 1 녹입니다.
Q만큼 반복하면서 위 과정을 반복하고, BFS를 이용해 가장 큰 그룹의 크기, 남아 있는 얼음의 수를 구합니다.
아래는 BFS를 이용해 가장 큰 그룹의 크기를 구하는 코드입니다.
var queue: [(Int, Int)] = [(i, j)]
var index = 0
while index < queue.count {
let node = queue[index]
index += 1
for k in 0..<4 {
let nx = node.0 + dx[k]
let ny = node.1 + dy[k]
guard (0..<size) ~= nx, (0..<size) ~= ny, !visited[nx][ny] else {
continue
}
visited[nx][ny] = true
if map[nx][ny] > 0 {
queue.append((nx, ny))
}
}
}
maxCountResult = max(maxCountResult, queue.count)
마법사 상어와 비바라기 (BOJ 21610)
풀이 코드 : https://github.com/jeongju9216/Algorithm/blob/main/Swift/BOJ/20000/21610.swift
구름들을 일괄적으로 이동시켜야 하기 때문에 clouds라는 배열이 있습니다.
typealias Point = (x: Int, y: Int)
var clouds: [Point] = [(n-1, 0), (n-2, 0), (n-1, 1), (n-2, 1)]이 구름 배열을 이용해 비를 뿌리고, 구름을 없애는 등 작업을 진행합니다.
파이어볼 문제처럼 1과 N이 연결되어 있다는 점입니다.
따라서 이 문제에서도 범위 밖으로 이동하는 코드가 있습니다.
func moveCloud(_ direction: Int, _ moving: Int) {
let moving = moving % n
for i in 0..<clouds.count {
clouds[i].x = (clouds[i].x + moving * dx[direction] + n) % n
clouds[i].y = (clouds[i].y + moving * dy[direction] + n) % n
map[clouds[i].x][clouds[i].y] += 1
}
}
구름을 움직였다면 대각선 방향의 바구니 수만큼 물이 증가합니다.
stride를 이용한 이유는 방향 벡터가 ←, ↖, ↑, ↗, →, ↘, ↓, ↙로 총 8개이기 때문입니다.
2부터 시작해서 2 단위로 점프하면 대각선 벡터만 나옵니다.
func copyWater() {
for cloud in clouds {
var copyCount = 0
for direction in stride(from: 2, through: 8, by: +2) {
let nx = cloud.x + dx[direction]
let ny = cloud.y + dy[direction]
guard (0..<n) ~= nx, (0..<n) ~= ny else {
continue
}
if map[nx][ny] > 0 {
copyCount += 1
}
}
map[cloud.x][cloud.y] += copyCount
}
}
물을 복사했다면 구름을 생성시켜야 합니다.
주의할 점은 비를 내리고 없어진 구름 위치에서는 구름이 생기면 안 된다는 점입니다.
저는 기준 구름 배열은 그대로 두고 새로운 구름 배열을 만들 때 기존 배열에 없는 원소만 추가하도록 했습니다.
func createClouds() {
var newClouds: [Point] = []
for i in 0..<n {
for j in 0..<n {
if map[i][j] >= 2 && !clouds.contains(where: { $0 == (i, j) }) {
newClouds.append((i, j))
map[i][j] -= 2
}
}
}
clouds = newClouds
}
위 작업을 commands만큼 반복하고 flatMap을 이용해 2차원 배열을 1차원으로 변경하여 reduce를 이용해 합을 구했습니다.
let result = map.flatMap { $0 }.reduce(0, +)
print(result)
감사합니다.