백준 - 드래곤 커브(Swift)

백준 - 드래곤 커브(Swift)

 

 

 문제 설명

 

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

 나의 풀이

 

처음 문제를 봤을때는 잘 이해하지 못했다.

오른쪽 방향에 대해 시계방향으로 전환하면 아래쪽 방향이 되고 그것을 끝 점에 붙이면 아래에 가는 게 아닌가? 생각이 들었는데

그냥 현재의 드래곤 커브를 시계방향으로 90도 돌리는 것만 집중하면 되는 것이었다.

 

그래서 1세대, 2세대, 3세대를 그려보면서 규칙을 찾았는데 위로갔던 선분은 왼쪽으로, 왼쪽으로 갔던 선분은 아래로, 오른쪽으로 가는 선분은 위로 가는 규칙을 찾았다. 

이는 문제에서 0번부터 3번까지의 방향을 언급한 것과 동일했다. 

 

그래서 스택에 먼저 현재의 세대를 넣은 후 마지막 선분부터 빼면서 그 선분이 가르키는 방향을 토대로 1증가한 후 방문하는 것을 반복해서 문제를 풀었다.

 

import Foundation

let N = Int(readLine()!)!
var arr = [[Int]]()
var visited = Array(repeating: Array(repeating: false, count: 101), count: 101)

let dx = [0, -1, 0, 1]
let dy = [1, 0, -1, 0]
var result = 0
for _ in 0..<N {
    arr.append(readLine()!.components(separatedBy:" ").map{Int($0)!})
}

for element in arr {
    let x = element[1] // x좌표
    let y = element[0] // y좌표
    let d = element[2] // 방향
    let g = element[3] // 세대
    
    visited[x][y] = true
    var stack = [Int]()
    var nx = x + dx[d]
    var ny = y + dy[d]
    visited[nx][ny] = true
    stack.append(d)
    for _ in 0..<g { // 세대만큼 진행
        for j in stride(from: stack.count-1, through: 0, by: -1) {
            var k = stack[j] + 1
            if k == 4 { k = 0 }
            nx = nx + dx[k]
            ny = ny + dy[k]
            visited[nx][ny] = true
            stack.append(k)
        }
    }
}

for i in 0..<100 {
    for j in 0..<100 {
        if visited[i][j], visited[i+1][j], visited[i][j+1], visited[i+1][j+1] {
            result += 1
        }
    }
}
print(result)

 

 피드백

 

문제를 풀 때 드래곤커브들을 어떻게 90도회전시켜서 적용시키는 가에 대해서 고민을 했었는데 통째로 회전을하는 것이 아닌 각 위치에서 마지막 선분을 기준으로 이동하는 규칙이 있었다. 규칙을 통해 문제를 해결하는 능력이 필요하다.

 

아직 방향을 자유자재로 전환시키면서 코드작성하는 것에 서툰 것 같다. dx, dy변수로 두고 방향이 넘어갔을때는 0으로 두면서 방향에 익숙해져야한다.