[프로그래머스] 2020 KAKAO BLIND RECRUITMENT Coding Test 블럭 이동하기 Solution in Swift

문제 출처

프로그래머스

 

---

문제

  로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 무지는 0과 1로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 0은 빈칸을 1은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

  로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

 

  로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

  위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

 

  0과 1로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.

• board의 원소는 0 또는 1입니다.

• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.

• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

입출력 예

board	result
[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]	7

입출력 예에 대한 설명

문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.

 

 

---

Point

1. 입력값인 2차원 배열 맵에서 가로 2 세로 1 사이즈의 로봇이 장애물을 피해 (0, 0)에서 (n, n)까지 가는 최단시간을 찾는 문제이다.

 

2. 입력값 2차원 배열은 N*N 사이즈 이고 인덱스 값으로 0 또는 1이 주어지며 0은 통과 가능, 1은 장애물이다.

 

3. 로봇의 이동은 상하좌우로 움직일 수 있고 왼쪽 또는 오른쪽 지점을 기준으로 잡고 90도 회전도 가능하다.  한 이동에 걸리는 시간은 1초이며 회전은 회전 반경에 장애물이 없어야 가능하다.

 

 

---

Solution

	//
	// MoveBlock.swift
	// ProgrammingProblems
	//
	// Copyright © 2020 roseMelon. All rights reserved.
	//
	import Foundation
	struct State: Hashable {
	let point: Point
	let way: Way
	var subPoint: (Int, Int) {
	return way == .right ? (point.x, point.y + 1) : (point.x + 1, point.y)
	}
	func movableState() -> [State] {
	let move = [(point.x - 1, point.y), (point.x + 1, point.y), (point.x, point.y - 1), (point.x, point.y + 1)]
	.map { State(point: Point($0), way: way) }
	.filter { checkPointAvailable($0.point.toTuple()) && checkPointAvailable($0.subPoint) }
	.filter { !checkRecordExist($0) }
	let rotate = [(false, -1, -1), (false, 1, -1), (true, 1, 1), (true, -1, 1)]
	.map { elem -> State? in
	let checkPoint = elem.0 ? point.toTuple() : subPoint
	let add = way == .right ? (elem.1, elem.2) : (elem.2, elem.1)
	let next = elem.0 ? ((point.x + add.0, point.y + add.1), subPoint) : (point.toTuple(), (subPoint.0 + add.0, subPoint.1 + add.1))
	let sortedPoint = (next.0.0 - next.1.0 > 0 || next.0.1 - next.1.1 > 0) ? (next.1, next.0) : next
	let newRecord = State(point: Point(sortedPoint.0), way: way == .right ? .down : .right)
	guard checkPointAvailable(elem.0 ? next.0 : next.1) else { return nil }
	guard MAP[checkPoint.0 + (way == .right ? add.0 : 0)][checkPoint.1 + (way == .right ? 0 : add.1)] != 1 else { return nil }
	guard !checkRecordExist(newRecord) else { return nil }
	return newRecord
	}.filter { $0 != nil }.map { $0! }
	return move + rotate
	}
	enum Way {
	case right, down
	}
	}
	struct Point: Hashable {
	let x: Int
	let y: Int
	init(_ point: (Int, Int)) {
	self.x = point.0
	self.y = point.1
	}
	func toTuple() -> (Int, Int) { return (x,y) }
	}
	var MAP: [[Int]] = []
	var record: [Set<State>] = []
	func solution(_ board:[[Int]]) -> Int {
	MAP = board
	record.append([State(point: Point((0,0)), way: .right)])
	return run(counter: 1)
	}
	func run(counter: Int) -> Int {
	guard let last = record.last else { return 0 }
	if last.contains(State(point: Point((MAP.count - 1, MAP.count - 2)), way: .right))
	|| last.contains(State(point: Point((MAP.count - 2, MAP.count - 1)), way: .down)) {
	return counter - 1
	}
	var tmp: Set<State> = []
	for elem in last {
	elem.movableState().forEach { tmp.insert($0) }
	}
	record.append(tmp)
	return run(counter: counter + 1)
	}
	func checkPointAvailable(_ p: (Int,Int)) -> Bool {
	return p.0 < MAP.count && p.0 >= 0 && p.1 < MAP.count && p.1 >= 0 && MAP[p.0][p.1] != 1
	}
	func checkRecordExist(_ state: State) -> Bool {
	return record.reduce(false) { $0 || $1.contains(state) }
	}

view raw MoveBlock.swift hosted with ❤ by GitHub

 

---

2020 카카오 블라인드 채용 코딩 테스트 '블럭 이동하기' 스위프트 솔루션