[PCCP] Lv3: 경주로 건설(67259) 해설

문제

- 문제 링크: 경주로 건설

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: 보드의 한 변의 길이

- 너비 우서 탐색은 N * N개의 노드를 탐색하고 네 방향을 고려하므로 시간 복잡도는 O(N^2)

import java.util.ArrayDeque;

public class Solution {

    private static class Node {
        int x, y, direction, cost;

        public Node(int x, int y, int direction, int cost) {
            this.x = x;
            this.y = y;
            this.direction = direction;
            this.cost = cost;
        }
    }

    // 순서가 반드시 (0, -1), (-1, 0), (0, 1), (1, 0) 순서로 되어야합니다. 코너 계산에 필요함
    private static final int[] rx = {0, -1, 0, 1};
    private static final int[] ry = {-1, 0, 1, 0};

    private static int N;
    private static int[][][] visited;

    // 주어진 좌표가 보드의 범위 내에 있는지 확인
    private static boolean isValid(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < N;
    }

    // 주어진 좌표가 차단되었거나 이동할 수 없는지 확인
    private static boolean isBlocked(int[][] board, int x, int y) {
        return (x == 0 && y == 0) || !isValid(x, y) || board[x][y] == 1;
    }

    // 이전 방향과 현재 방향에 따라 비용 계산
    private static int calculateCost(int direction, int prevDirection, int cost) {
        if (prevDirection == -1 || (prevDirection - direction) % 2 == 0)
            return cost + 100;
        return cost + 600;
    }

    // 주어진 좌표와 방향이 아직 방문하지 않았거나 새 비용이 더 작은 경우
    private static boolean isShouldUpdate(int x, int y, int direction, int newCost) {
        return visited[x][y][direction] == 0 || visited[x][y][direction] > newCost;
    }

    public int solution(int[][] board) {
        ArrayDeque<Node> queue = new ArrayDeque<>();
        queue.add(new Node(0, 0, -1, 0));
        N = board.length;
        visited = new int[N][N][4];

        int answer = Integer.MAX_VALUE;

        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            Node now = queue.poll();

            // 가능한 모든 방향에 대해 반복
            for (int i = 0; i < 4; i++) {
                int new_x = now.x + rx[i];
                int new_y = now.y + ry[i];

                // 이동할 수 없는 좌표는 건너뛰기
                if (isBlocked(board, new_x, new_y)) {
                    continue;
                }

                int new_cost = calculateCost(i, now.direction, now.cost);

                // 도착지에 도달한 경우 최소 비용 업데이트
                if (new_x == N - 1 && new_y == N - 1) {
                    answer = Math.min(answer, new_cost);
                }
                // 좌표와 방향이 아직 방문하지 않았거나 새 비용이 더 작은 경우 큐에 추가
                else if(isShouldUpdate(new_x, new_y, i, new_cost)) {
                    queue.add(new Node(new_x, new_y, i, new_cost));
                    visited[new_x][new_y][i] = new_cost;
                }
            }
        }

        return answer;
    }

}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: 보드 한 변의 길이

- 너비 우선 탐색은 N*N개의 노드를 탐색하고 네 방향을 고려하므로 시간 복잡도: O(N^2)

def solution(board):
    # 주어진 좌표가 보드의 범위 내에 있는지 확인
    def is_valid(x, y):
        return 0 <= x < N and 0 <= y < N
        
    # 주어진 좌표가 차단되었거나 이동할 수 없는지 확인
    def is_blocked(x, y):
        return (x, y) == (0, 0) or not is_valid(x, y) or board[x][y] == 1
    
    # 이전 방향과 현재 방향에 따라 비용 계산
    def calculate_cost(direction, prev_direction, cost):
        if prev_direction == -1 or (prev_direction - direction) % 2 == 0:
            return cost + 100
        else:
            return cost + 600
        
    # 주어진 좌표와 방향이 아직 방문하지 않았거나 새 비용이 더 작은 경우
    def isShouldUpdate(x, y, direction, new_cost):
        return visited[x][y][direction] == 0 or visited[x][y][direction] > new_cost
        
    queue = [(0, 0, -1, 0)]
    N = len(board)
    directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
    visited = [[[0 for _ in range(4)] for _ in range(N)] for _ in range(N)]
    answer = float("inf")
    
    # 큐가 빌 때까지 반복
    while queue:
        x, y, prev_direction, cost = queue.pop(0)
        
        # 가능한 모든 방향에 대해 반복
        for direction, (dx, dy) in enumerate(directions):
            new_x, new_y = x + dx, y + dy
            
            # 이동할 수 없는 좌표는 건너뛰기
            if is_blocked(new_x, new_y):
                continue
            
            new_cost = calculate_cost(direction, prev_direction, cost)
            
            # 도착지에 도달한 경우 최소 비용 업데이트
            if (new_x, new_y) == (N - 1, N - 1):
                answer = min(answer, new_cost)
            # 좌표와 방향이 아직 방문하지 않았거나 새 비용이 더 작은 경우 큐에 추가
            elif isShouldUpdate(new_x, new_y, direction, new_cost):
                queue.append((new_x, new_y, direction, new_cost))
                visited[new_x][new_y][direction] = new_cost
    return answer

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: 보드의 한 변의 길이

- 너비우선탐색은 N*N개의 노드를 탐색하고 네방향을 고려: O(N^2)

class Queue {
    items = [];
    front = 0;
    rear = 0;

    push(item) {
        this.items.push(item);
        this.rear++;
    }

    first() {
        return this.items[this.front];
    }

    last() {
        return this.items[this.rear - 1];
    }

    pop() {
        return this.items[this.front++];
    }

    isEmpty() {
        return this.front === this.rear;
    }
}

function solution(board) {
    // 주어진 좌표가 보드의 범위 내에 있는지 확인
    function isValid(x, y) {
        return 0 <= x && x < N && 0 <= y && y < N;
    }
    
    // 주어진 좌표가 차단되었거나 이동할 수 없는지 확인
    function isBlocked(x, y) {
        return (x === 0 && y === 0 || !isValid(x, y) || board[x][y] === 1);
    }
    
    // 이전 방향과 현재 방향에 따라 비용을 계산
    function calculateCost(direction, preDirection, cost) {
        if (preDirection === -1 || (preDirection - direction) % 2 === 0) {
            return cost + 100;
        } else {
            return cost + 600;
        }
    }
    
    // 주어진 좌표와 방향이 아직 방문하지 않았거나 새 비용이 더 작은 경우
    function isShouldUpdate(x, y, direction, new_cost) {
        return visited[x][y][direction] === 0 || visited[x][y][direction] > new_cost;
    }
    
    const queue = new Queue();
    queue.push([0, 0, -1, 0]);
    const N = board.length;
    const directions = [
        [0, -1],
        [-1, 0],
        [0, 1],
        [1, 0],
    ];

    const visited = Array.from({ length: N }, () =>
        Array.from({ length: N }, () => Array(4).fill(0))
    );
    let answer = Infinity;

    
    // 큐가 빌 때까지 반복
    while (!queue.isEmpty()) {
        const [x, y, prevDirection, cost] = queue.pop();

        // 가능한 모든 방향에 대해 반복
        for (let direction = 0; direction < 4; direction++) {
            const [dx, dy] = directions[direction];
            const newX = x + dx;
            const newY = y + dy;
            
            // 이동할 수 없는 좌표는 건너뛰기
            if (isBlocked(newX, newY)) {
                continue;
            }

            const new_cost = calculateCost(direction, prevDirection, cost);
    
            // 도착지에 도달한 경우 최소 비용 업데이트
            if (newX === N - 1 && newY === N - 1) {
                answer = Math.min(answer, new_cost);
            }
       
            // 좌표와 방향이 아직 방문하지 않았거나 새 비용이 더 작은 경우 큐에 추가
            else if (isShouldUpdate(newX, newY, direction, new_cost)) {
                queue.push([newX, newY, direction, new_cost]);
                visited[newX][newY][direction] = new_cost;
            }
        }
    }

    return answer;
}

solution 2)

import

solution 3)

import