[백준/Swift] 20057번: 마법사 상어와 토네이도
https://www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
문제 제목만 봐도 머리가 어질 하다
분명 굉장히 킨 코드를 짜야할 거 같은 느낌이 드는...
구현 문제였는데 이 문제는 처음에 풀었을 때 2시간 동안 풀었는데 결국 해결하지 못했다.
이 마법사 상어 문제를 풀면서 느낀 건
구현 문제는 문제가 원하는 것이 무엇인지 제대로 알고, 조건을 꼼꼼하게 체크해야 하는 거 같다.
기능 메소드들도 구분하고, 기능들이 나누어지는데 여기서 음 이 메소드는 맞을 거야! 하고 넘어간 부분에서 틀려서 굉장히 오래 헤맬 수도 있다. (이 문제에서 내가 그럼) 하나의 메소드를 만들면 그게 맞는지 디버깅해 보는 습관을 가져야겠다!
문제 구현 방법에 대해 말해보자.우선, 나는 2가지로 나눴다.1. 토네이도 이동2. 모래 흩날리기
여기서 토네이도는 반시계 방향으로 돌아가는데 2개의 방향에서 동일한 횟수로 이동한다.그러니까, 5x5 격자의 경우
L 방향으로 1회
D 방향으로 1회
R 방향으로 2회
U 방향으로 2회
L 방향으로 3회
D 방향으로 3회
R 방향으로 4회
U 방향으로 4회
L 방향으로 4회
2개의 방향에서, 그 방향으로 토네이도가 동일한 횟수만큼 이동한다.
마지막 L 방향에서는 이전 횟수와 동일하게 진행되는 것을 확인한다. 사실, 이 부분은 (0,-1)까지 가게 되는데 이 부분은 제외해 주면 된다.
while true {
for _ in 0..<2 { //두 개의 방향
for _ in 0..<movingNumber { //이동 횟수
curX += dir[direction][0]
curY += dir[direction][1]
flutterSand(direction, &array)
}
//direction 바꾸기
direction = (direction + 1) % 4
}
movingNumber += 1
if movingNumber == n { //마지막
for _ in 0..<movingNumber {
curX += dir[direction][0]
curY += dir[direction][1]
if (0..<n) ~= curX, (0..<n) ~= curY {
flutterSand(direction, &array)
}
}
break
}
}
모래 흩날리기 부분은 mask로 겹쳐서 진행했다.
여기서 알파 지역은 (y의 모래의 양 - 다른 지역으로 날아간 모래의 양)을 더해줘야 한다.
mask는 4개고, 좌/하/우/상 순서로 만들었다.
let masks = [ //좌 하 우 상
[[0, 0, 2, 0, 0], [0, 10, 7, 1, 0], [5, -1, 0, 0, 0], [0, 10, 7, 1, 0], [0, 0, 2, 0, 0]],
[[0, 0, 0, 0, 0], [0, 1, 0, 1, 0], [2, 7, 0, 7, 2], [0, 10, -1, 10, 0], [0, 0, 5, 0, 0]],
[[0, 0, 2, 0, 0], [0, 1, 7, 10, 0], [0, 0, 0, -1, 5], [0, 1, 7, 10, 0], [0, 0, 2, 0, 0]],
[[0, 0, 5, 0, 0], [0, 10, -1, 10, 0], [2, 7, 0, 7, 2], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0]]
]이건
이렇게 된 Mask
y 위치 좌표값에 curX와 curY를 맞춰야 한다. 이 mask는 5x5 사이즈이기 때문에 y 위치를 0,0으로 가정하면
좌측 상단에서부터
(-2,-2) (-2,-1) (-2,0) (-2,1) (-2,2)
(-1,-2) (-1,-1) (-1,0) (-1,1) (-1,2)
(0,-2) (0,-1) (0,0) (0,1) (0,2)
(1,-2) (1,-1) (1,0) (1,1) (1,2)
(2,-2) (2,-1) (2,0) (2,1) (2,2)
이런 식으로 되기 때문에 -2를 해주면 (0,0) ~ (4,4)가 나온다.
알파는 남은 모래를 얻기 때문에 mask 순회가 끝나고, 순회하는 동안 알아냈던 알파의 x, y에 넣어준다/answer에 넣어준다.
여기서 격자 밖으로 나갔다면 answer에 흩날린 모래 양을 넣어주고, 격자 안이라면 array의 해당 좌표에 넣어준다.
private func flutterSand(_ d: Int, _ array: inout [[Int]]) {
guard array[curX][curY] != 0 else { return } //모래양이 0이면 할 필요 없음
let sand = array[curX][curY] //y 위치의 모래 양
var tmp = sand
var (x, y) = (0, 0)
array[curX][curY] = 0 //모래 다 날아감~
//MASK에 맞춰서 진행
for i in 0..<5 {
for j in 0..<5 {
guard masks[d][i][j] != 0 else { continue } //비율 없는 곳 or x, y -> pass
if masks[d][i][j] == -1 { //알파라면
(x, y) = (i, j)
continue
}
//1. 해당 위치로 날아간 모래 양 구하기
let amount = sand * masks[d][i][j] / 100
tmp -= amount
//2. 범위 체크 (격자 밖으로 나갔는지 안나갔는지)
let nx = curX + i - 2
let ny = curY + j - 2
if (0..<n) ~= nx, (0..<n) ~= ny { //격자 밖으로 안나감
array[nx][ny] += amount //흩날려간 모래 양 더하기
} else { //격자 밖으로 나감
answer += amount //격자 밖으로 나간 모래 양 더하기
}
}
}
//알파 계산
let nx = curX + x - 2
let ny = curY + y - 2
if (0..<n) ~= nx, (0..<n) ~= ny { //격자 밖으로 안나감
array[nx][ny] += tmp //흩날려간 모래 양 더하기
} else { //격자 밖으로 나감
answer += tmp //격자 밖으로 나간 모래 양 더하기
}
}
[전체 코드]
import Foundation
//input
let n = Int(readLine()!)!
var array = [[Int]]()
for _ in 0..<n {
array.append(readLine()!.split(separator: " ").map{ Int(String($0))! })
}
//좌표 가운데에서 시작
var curX = n / 2
var curY = n / 2
var answer = 0
var movingNumber = 1 //같은 방향으로 몇 회 이동할지
var direction = 0 //왼쪽 방향부터 시작
let dir = [[0,-1], [1,0], [0,1], [-1,0]]
let masks = [ //좌 하 우 상
[[0, 0, 2, 0, 0], [0, 10, 7, 1, 0], [5, -1, 0, 0, 0], [0, 10, 7, 1, 0], [0, 0, 2, 0, 0]],
[[0, 0, 0, 0, 0], [0, 1, 0, 1, 0], [2, 7, 0, 7, 2], [0, 10, -1, 10, 0], [0, 0, 5, 0, 0]],
[[0, 0, 2, 0, 0], [0, 1, 7, 10, 0], [0, 0, 0, -1, 5], [0, 1, 7, 10, 0], [0, 0, 2, 0, 0]],
[[0, 0, 5, 0, 0], [0, 10, -1, 10, 0], [2, 7, 0, 7, 2], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0]]
]
//flutteringSandList의 중심(2,2)에 curX, curY를 맞추고 진행
private func flutterSand(_ d: Int, _ array: inout [[Int]]) {
guard array[curX][curY] != 0 else { return } //모래양이 0이면 할 필요 없음
let sand = array[curX][curY] //y 위치의 모래 양
var tmp = sand
var (x, y) = (0, 0)
array[curX][curY] = 0 //모래 다 날아감~
//MASK에 맞춰서 진행
for i in 0..<5 {
for j in 0..<5 {
guard masks[d][i][j] != 0 else { continue } //비율 없는 곳 or x, y -> pass
if masks[d][i][j] == -1 { //알파라면
(x, y) = (i, j)
continue
}
//1. 해당 위치로 날아간 모래 양 구하기
let amount = sand * masks[d][i][j] / 100
tmp -= amount
//2. 범위 체크 (격자 밖으로 나갔는지 안나갔는지)
let nx = curX + i - 2
let ny = curY + j - 2
if (0..<n) ~= nx, (0..<n) ~= ny { //격자 밖으로 안나감
array[nx][ny] += amount //흩날려간 모래 양 더하기
} else { //격자 밖으로 나감
answer += amount //격자 밖으로 나간 모래 양 더하기
}
}
}
//알파 계산
let nx = curX + x - 2
let ny = curY + y - 2
if (0..<n) ~= nx, (0..<n) ~= ny { //격자 밖으로 안나감
array[nx][ny] += tmp //흩날려간 모래 양 더하기
} else { //격자 밖으로 나감
answer += tmp //격자 밖으로 나간 모래 양 더하기
}
}
while true {
for _ in 0..<2 {
for _ in 0..<movingNumber {
curX += dir[direction][0]
curY += dir[direction][1]
flutterSand(direction, &array)
}
//direction 바꾸기
direction = (direction + 1) % 4
}
movingNumber += 1
if movingNumber == n { //마지막
for _ in 0..<movingNumber {
curX += dir[direction][0]
curY += dir[direction][1]
if (0..<n) ~= curX, (0..<n) ~= curY {
flutterSand(direction, &array)
}
}
break
}
}
print(answer)
1트때 실패했던 건 다름 아닌 토네이도 이동!
사실 토네이도 이동은 나름 쉬웠기 때문에 이게 맞겠지~ 하고 모래 흩날리는 부분에서 오류가 있을 거라고 생각하고 그 부분만 봤었는데
오늘 다시 처음 하는 마음가짐으로 풀어보니 토네이도 이동 부분이 문제였다!
이런 삽질로 얻은 건 구현 문제는
1. 규칙 / 조건 꼼꼼히 살피고 설계 먼저 하기 (꼭 코드먼저 짜려고 손이 나간다)
2. 순서대로 구현하면서 그냥 넘어가지 말고 제대로 코드를 짰는지 디버깅하기
전에 실패했던 구현 문제도 다시 풀어봐야겠다!
