[Swift]BOJ-3190

BOJ-3190, 뱀

문제 📑

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

3190번: 뱀

 

문제 정리 ▾

BOJ-3190

• 보드의 크기는 N*N으로 N에 대한 입력을 받는다.
• 초기 뱀의 길이는 1이며, 뱀의 머리는 오른쪽을 향한다.
• 뱀은 1초에 1칸씩 움직이며 아래의 규칙이 적용된다.
• 뱀의 방향 전환으로는 D는 오른쪽으로 90도 회전, L은 왼쪽으로 90도 회전이다.

• 먼저 뱀은 몸 길이를 늘려 머리를 다음 칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸 길이를 줄여서 꼬리가 위치한 칸을 비워준다.
  즉, 몸 길이는 변하지 않는다.

 

접근 🚶🏻

나의 생각 ▾

• 해당 문제는 BFS알고리즘과 비슷하게 응용해서 풀면 될 것 같다. 하나를 깊게 들어가기보단 머리의 방향에 맞게 이동을 하기 때문에 그 방향에 맞게 이동해주면서 보드 밖이나 몸을 만나는 경우에 break 시켜주면 될 것 같다.
• 내가 만든 2차원 배열(board)에 아래와 같이 표현할 것 같다.
  • 빈칸: 0
  • 뱀(몸): 1
  • 사과: 2
• 뱀은 queue로 비유를 하여, 사과를 못만날 땐 removeFirst()를 통해 좌표(인덱스)를 받아 해당 칸을 0으로 바꿔주면 되고, 사과가 있다면 append() 및 해당 칸을 1로 바꿔주면 될것으로 보인다.

 

내 코드 ▾

import Foundation

let N = Int(readLine()!)!
var board = Array(repeating: Array(repeating: 0, count: N), count: N)
var visited = Array(repeating: Array(repeating: false, count: N), count: N)
let K = Int(readLine()!)!

for _ in 0..<K {
    let data = readLine()!.split(separator: " ").map{ Int($0)!-1 }
    board[data[0]][data[1]] = 2
}

let L = Int(readLine()!)!
var move_dir = [Int: Int]()

for _ in 0..<L {
    let data = readLine()!.split(separator: " ")
    move_dir[Int(data[0])!] = data[1] == "D" ? 1 : 3
}

let dx = [0, 1, 0, -1]
let dy = [1, 0, -1, 0]

func is_valid_coord(_ x: Int, _ y: Int) -> Bool {
    return (0 <= x && x < N) && (0 <= y && y < N)
}

var cnt: Int = 0
var snake = [(Int, Int)]()
snake.append((0, 0))
board[0][0] = 1

var x = 0
var y = 0
var d = 0

while true {
    cnt += 1
    x = x + dx[d]
    y = y + dy[d]

    if !is_valid_coord(x, y) || board[x][y] == 1 { break }

    if board[x][y] == 0 {
        snake.append((x, y))
        board[x][y] = 1
        let dt = snake.removeFirst()
        board[dt.0][dt.1] = 0
    }
    else if board[x][y] == 2 {
        snake.append((x, y))
        board[x][y] = 1
    }
    
    for (key, value) in move_dir {
        if cnt == key { d = (d+value)%4 }
    }
}

print(cnt)

• 방향 전환
  • 방향 전환에 대한 값을 어떻게 표현해서 해당 cnt일 때 방향을 바꿔줄까 하다가 Dictionary로 구현을 해보았다.
  • 해당 과정에서 Dictionary를 반복적으로 검사해야하는 부분이 마음에 걸렸으나 L의 최대 크기는 100으로 많이 돌릴 것 같지 않아 무방할것으로 판단하고 넘겼다.
• 전반적인 프로세스
  • 뱀 이동할 칸을 검색하여 0,1,2에 맞춰 아래와 같이 처리해준다.
    • 0(빈 칸): 뱀을 빈 칸으로 이동시키며 해당 칸의 값을 1로 바꿔주고, 이 전의 좌표(인덱스)를 queue에서 지워주면서 칸의 값을 0으로 바꿔준다.
    • 1(뱀의 몸): while문을 break 시켜 종료시킨다.
    • 2(사과): 뱀(queue)에 해당 좌표를 넣어주고, 좌표(인덱스) 칸의 값을 1로 바꿔준다.

 

 

Addtional 📂

• 제약 조건이 그렇게 까다롭진 않았지만 뱀을 queue로 비유를 하는지에 대한 부분이 컸던 것 같다.
• 방향 전환을 어떻게 구현할지에서 생각을 많이 했던 것 같다.
• 요즘 시뮬레이션 문제를 풀고 있지만 가장 중요한 부분은 지문을 잘 이해하는지인 것 같다.. 어릴 때 책을 많이 읽어둘 걸 그랬다..