728x90
반응형
programmers.co.kr/learn/courses/30/lessons/67259
코딩테스트 연습 - 경주로 건설
[[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[
programmers.co.kr
안녕하세요 후르륵짭짭 입니다.
처음에 이 문제를 DFS로 풀었습니다.
그런데 시간초과,,,,, 왜 시간 초과인지 곰곰히 생각했는데,,,
DFS일 경우에는 모든 경우에 대해서 쭉들어 갔다가 쭉 나오기 때문에,,, 좋지 못한 방법 이였습니다.
따라서 최단거리를 구하는 문제에서 BFS를 구하는게 좋을 것 같습니다ㅣ.
더보기
var check : [[Bool]] = []
var LR : [Int] = [1,-1,0,0]
var UD : [Int] = [0,0,1,-1]
var minValue : Int = Int.max
var allCnt = 0
func solution(_ board:[[Int]]) -> Int {
check = Array(repeating: Array(repeating: true, count: board.count), count: board.count)
check[0][0] = false
dfs(0, 0, -1, board, 0, 0)
print(allCnt)
return minValue
}
func dfs(_ currentX : Int , _ currentY : Int ,_ before : Int ,_ board : [[Int]],_ corner : Int,_ cnt : Int){
if currentX == board.count - 1 && currentY == board.count - 1 {
let total = ( corner * 500 ) + (cnt * 100)
allCnt += 1
minValue = min(total, minValue)
// for element in check{
// print(element)
// }
//
}
else{
for start in 0..<4 {
let nextX = currentX + LR[start]
let nextY = currentY + UD[start]
if nextX >= 0 && nextX < board.count && nextY >= 0 && nextY < board.count {
if check[nextY][nextX] && board[nextY][nextX] == 0{
check[nextY][nextX] = false
if (0...1).contains(before) {
// print("before LR")
//코너를 돌았다
if (2...3).contains(start){
// print("next corner")
let total = ((corner + 1) * 500 ) + ( (cnt + 1 ) * 100)
if minValue > total{
dfs(nextX, nextY, start, board, corner + 1, cnt + 1)
}
}else{
// print("next 직선")
let total = ((corner) * 500 ) + ( (cnt + 1 ) * 100)
if minValue > total{
dfs(nextX,nextY, start, board, corner , cnt + 1)
}
}
}
else if (2...3).contains(before){
// print("before UD")
if (2...3).contains(start){
// print("next 직선")
let total = ((corner) * 500 ) + ( (cnt + 1 ) * 100)
if minValue > total{
dfs(nextX,nextY, start, board, corner , cnt + 1)
}
}
//코너를 돌았다.
else{
// print("next corner")
let total = ((corner + 1) * 500 ) + ( (cnt + 1 ) * 100)
if minValue > total{
dfs(nextX, nextY, start, board, corner + 1, cnt + 1)
}
}
}
else{
dfs(nextX,nextY, start, board,corner, cnt + 1)
}
check[nextY][nextX] = true
}
}
}
}
}
** 저의 풀이 **
func solution(_ board:[[Int]]) -> Int {
let LR : [Int] = [1,-1,0,0]
let UD : [Int] = [0,0,1,-1]
var check : [[Int]] = Array(repeating: Array(repeating: Int.max, count: board.count), count: board.count)
var queue : [(x : Int , y : Int , before : Int , cnt : Int, corner : Int)] = []
queue.append((0,0,-1,0,0))
check[0][0] = 0
while !queue.isEmpty{
let item = queue.first!
var next_queue = queue[1..<queue.count]
let x = item.x
let y = item.y
let before = item.before
let cnt = item.cnt
let corner = item.corner
for next in 0..<4{
let nextX = x + LR[next]
let nextY = y + UD[next]
if (0..<board.count).contains(nextX) && (0..<board.count).contains(nextY){
if board[nextY][nextX] == 0 {
if (0...1).contains(before){
//코너를 돌았다
if (2...3).contains(next){
let total = (corner + 1) * 500 + (cnt + 1) * 100
if check[nextY][nextX] >= total {
check[nextY][nextX] = total
next_queue.append((x: nextX, y: nextY, before: next, cnt: cnt + 1, corner: corner + 1))
}
}
//아니다
else{
let total = corner * 500 + (cnt + 1) * 100
if check[nextY][nextX] >= total {
check[nextY][nextX] = total
next_queue.append((x: nextX, y: nextY, before: next, cnt: cnt + 1, corner: corner))
}
}
}
else if (2...3).contains(before){
//코너를 돌았다
if (0...1).contains(next){
let total = (corner + 1) * 500 + (cnt + 1) * 100
if check[nextY][nextX] >= total {
check[nextY][nextX] = total
next_queue.append((x: nextX, y: nextY, before: next, cnt: cnt + 1, corner: corner + 1))
}
}
//아니다
else{
let total = (corner) * 500 + (cnt + 1) * 100
if check[nextY][nextX] >= total {
check[nextY][nextX] = total
next_queue.append((x: nextX, y: nextY, before: next, cnt: cnt + 1, corner: corner))
}
}
}
else{
let total = (corner) * 500 + (cnt + 1) * 100
if check[nextY][nextX] >= total {
check[nextY][nextX] = total
next_queue.append((x: nextX, y: nextY, before: next, cnt: cnt + 1, corner: corner))
}
}
}
}
}
queue = Array(next_queue)
}
// for element in check{
// print(element)
// }
return check[board.count - 1][board.count - 1]
}
저는 이 문제를 이미 한번 DFS로 풀었기 때문에 BFS로 옮기는 것은 어렵지 않았습니다.
하지만 DFS로 풀면서 난감했던 부분을 다루도록 하겠습니다.
처음에 코너 문제로 헷갈렸습니다.
저는 처음에 코너에서 한번 이동하는 줄 알았는데, 그냥 몸체만 이동하는 거 였습니다.
따라서 직선으로 이동 까지 한다면 500 + 100의 총합인 600원이 드는 거 였는데, 이 문제를 푸는 당시에는 잘 몰랐습니다.
그리고 각 모든 경우에 대해서 예외 처리를 해주었습니다.
시작할 때는 무조건 직진 이기 때문에
else{
let total = (corner) * 500 + (cnt + 1) * 100
if check[nextY][nextX] >= total {
check[nextY][nextX] = total
next_queue.append((x: nextX, y: nextY, before: next, cnt: cnt + 1, corner: corner))
}
}무조건 queue에 넣어줬습니다.
if board[nextY][nextX] == 0 {
if (0...1).contains(before){
//코너를 돌았다
if (2...3).contains(next){
let total = (corner + 1) * 500 + (cnt + 1) * 100
if check[nextY][nextX] >= total {
check[nextY][nextX] = total
next_queue.append((x: nextX, y: nextY, before: next, cnt: cnt + 1, corner: corner + 1))
}
}
//아니다
else{
let total = corner * 500 + (cnt + 1) * 100
if check[nextY][nextX] >= total {
check[nextY][nextX] = total
next_queue.append((x: nextX, y: nextY, before: next, cnt: cnt + 1, corner: corner))
}
}
}
else if (2...3).contains(before){
//코너를 돌았다
if (0...1).contains(next){
let total = (corner + 1) * 500 + (cnt + 1) * 100
if check[nextY][nextX] >= total {
check[nextY][nextX] = total
next_queue.append((x: nextX, y: nextY, before: next, cnt: cnt + 1, corner: corner + 1))
}
}
//아니다
else{
let total = (corner) * 500 + (cnt + 1) * 100
if check[nextY][nextX] >= total {
check[nextY][nextX] = total
next_queue.append((x: nextX, y: nextY, before: next, cnt: cnt + 1, corner: corner))
}
}
}만약에 오른쪽 왼쪽으로 이전 했는데 다음에는 상 하로 이동하면 코너값과 이동량을 증가시켜줬습니다.
모든 경우에 대해서 예외 처리한다고 굉장히 코드가 길어진 것 같습니다.
아 그리고 갱신 할 때, 이 등호가 중요했습니다.
if check[nextY][nextX] >= total {왜냐하면 동일한 경우에도 넣어줘야하기 때문입니다.
728x90
반응형
댓글