[PCCP] Lv2: 미로 탈출(159993) 해설

문제

- 문제 링크: 미로 탈출

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: 지도 한 변의 길이

- isWithinRange()의 시간복잡도: O(1)

- findStartPoint()의 시간복잡도: O(N^2)

- 이동과정은 최악의 경우 지도의 크기가 N*N, 네 방향으로 이동하므로 시간 복잡도는 O(4*(N^2))

- 최종 시간 복잡도: O(N^2)

#include <queue>
#include <string>
#include <vector>

using namespace std;

// 현재 좌표, 해당 좌표까지 이동 횟수
struct Point {
    int y, x, cnt;
};

// 상하좌우로 이동하기 위한 오프셋
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int n, m;

// 현재 좌표가 유효한 좌표인지 확인
bool isWithRange(int y, int x) {
    return 0 <= y && y < n && 0 <= x && x < m;
}

// 시각 좌표 확인
Point findStartPoint(char start, vector<string>& maps) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (maps[i][j] == start) {
                return {i, j, 0};
            }
        }
    }
    return {-1, -1, -1}; // 시작점을 찾지 못한 경우
}

int bfs(char start, char end, vector<string>& maps) {
    bool visited[101][101] = {false}; // 방문 여부를 체크하는 배열
    queue<Point> q;
    
    q.push(findStartPoint(start, maps)); // 시작 노드부터 너비 우선 탐색하도록 추가
    
    while (!q.empty()) {
        Point current = q.front();
        q.pop();
        
        // 목적지에 도달했으면 해당 목적지까지 이동 횟수 반환
        if (maps[current.y][current.x] == end) {
            return current.cnt;
        }
        
        // 현재 위치 기준 상하좌우 확인
        for (int i = 0; i < 4; ++i) {
            int ny = current.y + dy[i];
            int nx = current.x + dx[i];
            
            if (isWithRange(ny, nx) && !visited[ny][nx] && maps[ny][nx] != 'X') {
                // 후보 좌표가 미로 범위 내에 있고, 아직 방문하지 않았으면 탐색 대상에 추가
                q.push({ny, nx, current.cnt + 1});
                visited[ny][nx] = true;
            }
        }
    }
    return -1;
}

int solution(vector<string> maps) {
    n = maps.size();
    m = maps[0].size();
    
    // 시작 지점부터 L까지 최단 거리를 구함
    int distanceToL = bfs('S', 'L', maps);
    if (distanceToL == -1)
        return -1;
   
   // L부터 도착지점까지 최단거리를 구함
   int distanceToE = bfs('L', 'E', maps);
   return distanceToE == -1 ? -1 : distanceToL + distanceToE;
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: 지도 한 변의 길이

- 이동 과정은 최악의 경우 지도의 크기가 N*N, 네 방향으로 이동하므로 시간 복잡도는 O(4*(N^2))

- 최종 시간 복잡도: O(N^2)

import java.util.ArrayDeque;

public class Solution {

    // 위, 아래, 왼쪽, 오른쪽 이동 방향
    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};

    // 위치 정보(x, y)를 저장할 클래스 생성
    private static class Point {
        int nx, ny;

        public Point(int nx, int ny) {
            this.nx = nx;
            this.ny = ny;
        }
    }

    private static char[][] map;
    private static int N, M;

    public int solution(String[] maps) {
        N = maps.length;
        M = maps[0].length();

        // 미로에 대한 정보를 배열로 저장
        map = new char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = maps[i].toCharArray();
        }

        Point start = null, end = null, lever = null;

        // 시작 지점, 출구 그리고 레버의 위치를 찾음
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 'S') start = new Point(j, i);
                else if (map[i][j] == 'E') end = new Point(j, i);
                else if (map[i][j] == 'L') lever = new Point(j, i);
            }
        }

        // 시작 자점 -> 레버, 레버 -> 출구까지의 최단 거리를 각각 구함
        int startLever = bfs(start, lever);
        int leverEnd = bfs(lever, end);

        // 도착 불가능한 경우는 -1, 도착 가능한 경우는 최단 거리를 반환
        if (startLever == -1 || leverEnd == -1)
            return -1;
        else
            return startLever + leverEnd;
    }

    // start -> end 로 너비 우선 탐색하여 최단거리 반환
    private static int bfs(Point start, Point end) {
        // 너비 우선 탐색 초기 과정
        int[][] dist = new int[N][M];
        ArrayDeque<Point> queue = new ArrayDeque<>();

        dist[start.ny][start.nx] = 1;
        queue.add(start);

        while (!queue.isEmpty()) {
            Point now = queue.poll();

            // 네 방향으로 이동
            for (int i = 0; i < 4; i++) {
                int nextX = now.nx + dx[i];
                int nextY = now.ny + dy[i];

                // 범위를 벗어나는 경우 예외 처리
                if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N)
                    continue;

                // 이미 방문한 지점인 경우 탐색하지 않음
                if (dist[nextY][nextX] > 0)
                    continue;

                // X가 아닌 지점만 이동 가능
                if (map[nextY][nextX] == 'X')
                    continue;

                // 거리 1증가
                dist[nextY][nextX] = dist[now.ny][now.nx] + 1;

                // 다음 정점을 큐에 넣음
                queue.add(new Point(nextX, nextY));

                // 도착점에 도달하면 최단 거리를 반환
                if (nextX == end.nx && nextY == end.ny)
                    return dist[end.ny][end.nx] - 1;
            }
        }

        // 탐색을 종료할 때까지 도착 지점에 도달하지 못 했다면 -1 반환
        return -1;
    }

}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: 지도 한 변의 길이

- is_valid_move()와 append_to_queue()의 시간 복잡도: O(1)

- 이동 과정은 최악의 경우 지도의 크기가 N*N, 네 방향으로 이동하므로 시간 복잡도: O(4*(N^2))

- 최종 시간 복잡도: O(N^2)

from collections import deque

# 이동 가능한 좌표인지 판단하는 함수
def is_valid_move(ny, nx, n, m, maps):
    return 0 <= ny < n and 0 <= nx < m and maps[ny][nx] != "X"
    
# 방문한 적이 없으면 큐에 넣고 방문 여부 표시
def append_to_queue(ny, nx, k, time, visited, q):
    if not visited[ny][nx][k]:
        visited[ny][nx][k] = True
        q.append((ny, nx, k, time + 1))
        
def solution(maps):
    n, m = len(maps), len(maps[0])
    visited = [[[False for _ in range(2)] for _ in range(m)] for _ in range(n)]
    # 위, 아래, 왼쪽, 오른쪽 이동 방향
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    q = deque()
    end_y, end_x = -1, -1
    
    # 시작점과 도착점을 찾아 큐에 넣고 방문 여부 표시
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                q.append((i, j, 0, 0))  # 시작점
                visited[i][j][0] = True
            if maps[i][j] == "E":
                end_y, end_x = i, j  # 도착점

    while q:
        y, x, k, time = q.popleft() # 큐에서 좌표와 이동 횟수를 꺼냄
        
        # 도착점에 도달하면 결과 반환
        if y == end_y and x == end_x and k == 1:
            return time
    
        # 네 방향으로 이동
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            # 이동 가능한 좌표인 때에만 큐에 넣음
            if not is_valid_move(ny, nx, n, m, maps):
                continue
        
            # 다음 이동 지점이 물인 경우
            if maps[ny][nx] == "L":
                append_to_queue(ny, nx, 1, time, visited, q)
            # 다음 이동 지점이 물이 아닌 경우
            else:
                append_to_queue(ny, nx, k, time, visited, q)
        
    # 도착점에 도달하지 못한 경우
    return -1

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: 지도 한변의 길이

- isValidMove()와 appendToQueue(): O(1)

- 이동 과정은 최악의 경우 지도의 크기가 N*N, 네 방향으로 이동하므로 시간복잡도: O(4*(N^2))

- 최종 시간 복잡도: O(N^2)

class Queue {
    items = [];
    front = 0;
    rear = 0;
    
    push(item) {
        this.items.push(item);
        this.rear++;
    }
    
    pop() {
        return this.items[this.front++];
    }
    
    isEmpty() {
        return this.front === this.rear;
    }
}

// 이동 가능한 좌표인지 판단하는 함수
function isValidMove(ny, nx, n, m, maps) {
    return 0 <= ny && ny < n && 0 <= nx && nx < m && maps[ny][nx] !== 'X';
}

// 방문한 적이 없으면 큐에 넣고 방문 여부 표시
function appendToQueue(ny, nx, k, time, visited, q) {
    if (!visited[ny][nx][k]) {
        visited[ny][nx][k] = true;
        q.push([ny, nx, k, time + 1]);
    }
}

function solution(maps) {
    const n = maps.length;
    const m = maps[0].length;
    const visited = Array.from(Array(n), () => Array(m).fill(false).map(() => Array(2).fill(false)));

    
    // 위, 아래, 왼쪽, 오른쪽 이동 방향
    const dy = [-1, 1, 0, 0];
    const dx = [0, 0, -1, 1];
    const q = new Queue();
    let endY = -1;
    let endX = -1;

    // 시작점과 도착점을 찾아 큐에 넣고 방문 여부 표시
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < m; ++j) {
            if (maps[i][j] === 'S') { // 시작점
                q.push([i, j, 0, 0]);
                visited[i][j][0] = true;
            }
            
            if (maps[i][j] === 'E') { // 도착점
                endY = i;
                endX = j;
            }
        }
    }
    
    while (!q.isEmpty()) {
        const [y, x, k, time] = q.pop(); // 큐에서 좌표와 이동 횟수를 꺼냄
        
        // 도착점에 도달하면 결과 반환
        if (y === endY && x === endX && k === 1) {
            return time;
        }
        
        // 네 방향으로 이동
        for (let i = 0; i < 4; ++i) {
            const ny = y + dy[i];
            const nx = x + dx[i];
            
            // 이동 가능한 좌표인 때에만 큐에 넣음
            if (!isValidMove(ny, nx, n, m, maps)) {
                continue;
            }
            
            // 다음 이동 지점이 레버인 경우
            if (maps[ny][nx] === 'L') {
                appendToQueue(ny, nx, 1, time, visited, q);
            } else { // 다음 이동 지점이 레버가 아닌 경우
                appendToQueue(ny, nx, k, time, visited, q);
            }
        }
    }

    // 도착점에 도달하지 못하는 경우
    return -1;
}

solution 2)

import

solution 3)

import