[PCCP] Lv2: 게임 맵 최단거리(1844) 해설

문제

- 문제 링크: 게임 맵 최단거리

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<vector>
#include <queue>
using namespace std;
 
int visited[101][101];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
 
int solution(vector<vector<int> > maps)
{
    int answer = 0;
    queue<pair<int,pair<int,int> > > q;
    q.push(make_pair(1,make_pair(0,0)));        // 시작 위치 넣기
    visited[0][0] = true;
    while (!q.empty())
    {
        int x = q.front().second.first;
        int y = q.front().second.second;
        int time = q.front().first;
        if (x == maps[0].size()-1 && y == maps.size() -1)   // 도착 지점 체크
        {
            answer = time;
            break;
        }
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && yy >= 0 && xx < maps[0].size() && yy< maps.size())       // 범위 지정
            {
                if (!visited[yy][xx] && maps[yy][xx] == 1)      // 방문했던 곳 and maps 상 길인 지점                                                     
                {
                    visited[yy][xx] = true;
                    q.push(make_pair(time +1, make_pair(xx,yy)));
                }
            }
        }
    }
    if (answer == 0)        // answer = 0 이면 위 bfs에서 도착지점을 못찾은것
        answer = -1;
    return answer;
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N * M: 배열의 크기

- dist 배열을 초기화: O(N*M)

- 너비우선탐색을 할 때는 최악의 경우 dist의 모든 위치가 큐에 들어가는 경우이므로 시간 복잡도는 O(N *M)

- 최종 시간 복잡도: O(N* M)

import java.util.ArrayDeque;

class Solution {
    // 이동할 수 있는 방향을 나타내는 배열 rx, ry 선언
    private static final int[] rx = {0, 0, 1, -1};
    private static final int[] ry = {1, -1, 0, 0};
    
    private static class Node {
        int r, c;
        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    
    public int solution(int[][] maps) {
        // 맵의 크기를 저장하는 변수 선언
        int N = maps.length;
        int M = maps[0].length;
        
        // 최단 거리를 저장할 배열 생성
        int[][] dist = new int[N][M];
        
        // bfs 탐색을 위한 큐 생성
        ArrayDeque<Node> queue = new ArrayDeque<>();
        
        // 시작 정점에 대해서 큐에 추가, 최단 거리 저장
        queue.addLast(new Node(0, 0));
        dist[0][0] = 1;
        
        // queue가 빌 때까지 반복
        while (!queue.isEmpty()) {
            Node now = queue.pollFirst();
            
            // 현재 위치에서 이동할 수 있는 모든 방향
            for (int i = 0; i < 4; ++i) {
                int nr = now.r + rx[i];
                int nc = now.c + ry[i];
                
                // 맵 밖으로 나가는 경우 예외 처리
                if (nr < 0 || nc < 0 || nr >= N || nc >= M)
                    continue;
                
                // 벽으로 가는 경우 예외 처리
                if (maps[nr][nc] == 0)
                    continue;
                
                // 이동한 위치가 처음 방문하느 경우, queue에 추가하고 거리 갱신
                if (dist[nr][nc] == 0) {
                    queue.addLast(new Node(nr, nc));
                    dist[nr][nc] = dist[now.r][now.c] + 1;
                }
            }
        }
        
        // 목적지까지 최단 거리 반환, 목적지에 도달하지 못한 경우에는 -1 반환
        return dist[N - 1][M - 1] == 0 ? -1 : dist[N - 1][M -1];
        
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N*M: 배열의 크기

- dist 배열 초기화: O(N*M)

- 너비 우선 탐색을 할 때는 최악의 경우 dist의 모든 위치가 큐에 들어가는 경우이므로 시간 복잡도는 O(N * M)

- 최종 시간 복잡도: O(N * M)

from collections import deque

def solution(maps):
    # 이동할 수 있는 방향을 나타내는 배열 move 선언
    move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    
    # 맵의 크기를 저장하는 변수 선언
    n = len(maps)
    m = len(maps[0])
    
    # 거리를 저장하는 배열 dist를 -1로 초기화
    dist = [[-1] * m for _ in range(n)]
    
    # bfs 함수 선언
    def bfs(start):
        # deque를 선언, 시작 위치를 deque에 추가
        q = deque([start])
        dist[start[0]][start[1]] = 1
        
        # deque가 빌 때까지 반복
        while q:
            here = q.popleft()
            
            # 현재 위치에서 이동할 수 있는 모든 방향
            for direct in move:
                row, column = here[0] + direct[0], here[1] + direct[1]
                
                # 이동한 위치가 범위를 벗어난 경우 다음 방향으로 넘어감
                if row < 0 or row >= n or column < 0 or column >= m:
                    continue
                    
                # 이동한 위치에 벽이 있는 경우 다음 방향으로 넘어감
                if maps[row][column] == 0:
                    continue
                    
                # 이동한 위치가 처음 방문하는 경우, deque에 추가하고 거리 갱신
                if dist[row][column] == -1:
                    q.append([row, column])
                    dist[row][column] = dist[here[0]][here[1]] + 1

        # 거리를 저장하는 배열 dist를 반환
        return dist
        
    bfs([0, 0])
    
    # 목전지까지의 거리 반환, 목적지에 도달하지 못한 경우 -1 반환
    return dist[n - 1][m - 1]

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N*M: 배열의 크기

- dist 배열 초기화: O(N * M)

- 너비우선탐색의 최악의 경우 dist의 모든 위치가 큐에 들어가는 경우: O(N*M)

- 최종 시간복잡도: O(N*M)

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(maps) {
    // 이동할 수 있는 방향르 나타내는 배열 move 선언
    const move = [[-1, 0], [0, -1], [0, 1], [1, 0]];
    
    // 맵의 크기를 저장하는 변수 선언
    const n = maps.length;
    const m = maps[0].length;
    
    // 거리를 저장하는 배열 dist를 -1로 초기화
    const dist = Array.from({ length: n }, () => Array(m).fill(-1));
    
    // bfs 함수 선언
    function bfs(start) {
        // queue를 선언하고 시작 위치를 queue에 추가
        const q = new Queue();
        q.push(start);
        dist[start[0]][start[1]] = 1;
        
        // queue가 빌 때까지 반복
        while (!q.isEmpty()) {
            const here = q.pop();
            
            // 현재 위치에서 이동할 수 있는 모든 방향
            for (const [dx, dy] of move) {
                const row = here[0] + dx;
                const column = here[1] + dy;

                // 이동한 위치가 범위를 벗어난 경우 다음 방향으로 넘어감
                if (row < 0 || row >= n || column < 0 || column >= m) {
                    continue;
                }

                // 이동한 위치에 벽이 있는 경우 다음 방향으로 넘어감
                if (maps[row][column] === 0) {
                    continue;
                }

                // 이동한 위치가 처음 방문하는 경우, queue에 추가하고 거리 갱싱
                if (dist[row][column] === -1) {
                    q.push([row, column]);
                    dist[row][column] = dist[here[0]][here[1]] + 1;
                }
            }
        }
    
        return dist;
    }
    
    // 시작 위치에서 bfs() 함수를 호출하여 거리 계산
    bfs([0, 0]);

    // 목적지까지의 거리 반환, 목적지에 도달하지 못한 경우 -1을 반환
    return dist[n - 1][m - 1];
}

solution 2)

import

solution 3)

import