[Swift] 2020 KAKAO INTERNSHIP 경주로 건설

Problem

 

코딩테스트 연습 - 경주로 건설

---

Solution

 

해당 문제는 DFS로 풀어야 하는 문제입니다.

 

1. 자동차와 상하좌우 방향 모델을 만들어준다. (필수는 아님)

 

자동차에 필요한 x,y,price,prev와 상하좌우 방향을 enum으로 미리 만들어놔서 코드를 간결하게 했습니다.

 

struct Car {
    var x:Int,y:Int,price:Int,prev:Direction
}

enum Direction {
    case left,right,up,down
}

 

2. 어떤 곳을 들렸는지 확인해줄 배열을 만들어줍니다.

 

 var visited:[[Int]] = Array(repeating: Array(repeating:Int.max, count: board.count), count: board.count)

 

3. 처음 시작하는 방향 오른쪽과 아래쪽으로 재귀를 시작해줍니다.

 

처음엔 왼쪽과 위쪽으로 움직일 수 없으므로 두가지 방향으로 재귀를 해줍니다.

 

또한 무조건 직선 방향으로 움직일 수 밖에 없으므로 가격은 100으로 설정해줍니다.

 

 moveFourDirection(car: Car(x: 1, y: 0, price: 100, prev:.right),board: board,visited: &visited)
 moveFourDirection(car: Car(x: 0, y: 1, price: 100, prev:.down),board:board,visited: &visited)

 

4.  현재 위치가 가능한 위치인지 확인해줍니다.

 

먼저 x,y 모두 board안에 있는지 확인해주고 현재 위치가 벽인지 아닌지 확인해줍니다.

 

또한 visited에 저장되어 있는 가격이 현재 위치의 가격보다 적거나 같을 때만 움직여줍니다.

 

만약 현재 위치가 이미 저장되어 있는 가격보다 더 비싸다면 의미가 없으므로 멈춰줍니다.

 

func isEnabled(car:Car,board:[[Int]],visited:[[Int]]) -> Bool {
    return 0..<board.count ~= car.x && 0..<board.count ~= car.y && car.price <= visited[car.y][car.x] && board[car.y][car.x] == 0
}

 

5. 4가지 방향으로 재귀해줍니다.

 

먼저 visited에 현재 가격을 설정해주고 새로운 자동차는 방향에 따른 x와 y값을 더해줍니다.

 

만약 car의 이전 방향이 현재 이동하려는 방향과 똑같다면 직선이므로 100을 추가해주고 

 

아니라면 600을 추가해줍니다.

 

그리곤 새로운 visited를 넣고 재귀해줍니다.

 

func moveFourDirection(car:Car,board:[[Int]],visited:inout [[Int]]) {
    let direction:[Direction:(Int,Int)] = [.right:(1,0),.left:(-1,0),.down:(0,1),.up:(0,-1)]
    if isEnabled(car: car, board: board, visited: visited) {
        visited[car.y][car.x] = car.price
        for (key,value) in direction {
            var newCar = Car(x: car.x + value.0, y: car.y+value.1, price: car.price, prev: key)
            newCar.price += car.prev == key ? 100 : 600
            moveFourDirection(car: newCar, board: board, visited: &visited)
        }
    }
}

 

6. visited의 가장 끝에 있는 도착점의 가격을 반환해줍니다.

 

return visited.last!.last!

---

Source Code

 

---

P.S

 

처음엔 BFS로 풀어야 하는 문제인지 알고 BFS로 풀었더니 테스트 케이스 25번 빼고 다 맞았다..

 

이게 함정이었음.. 그래서 당연히 BFS로 풀어야하고 엣지 케이스가 있구나 싶어서 계속 엣지 케이스를 찾다가 

 

결국 아 DFS로 풀어야하는 문제이구나를 깨닫고 DFS로 바꿨더니 바로 통과가 되었다...