[프로그래머스] 게임 맵 최단거리 Python, C++

https://school.programmers.co.kr/learn/courses/30/lessons/1844https://school.programmers.co.kr/learn/courses/30/lessons/1844https://school.programmers.co.kr/learn/courses/30/lessons/1844https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

(1) C++

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;
typedef pair<int, pair<int,int>> p;
int visited[101][101];
int N, M, x, y;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    M = maps[0].size();
    N = maps.size();
    queue<p> q;
    q.push(make_pair(1, make_pair(0, 0)));
    visited[0][0] = 1;
    while(!q.empty()){
        x = q.front().second.first;
        y = q.front().second.second;
        int time = q.front().first;
        if(x == N - 1 && y == M - 1){
            answer = time;
            break;
        }
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M ){
                if(visited[nx][ny] == 0&& maps[nx][ny] == 1){
                    visited[nx][ny] = 1;
                    q.push(make_pair(time + 1, make_pair(nx, ny)));
                }
            }
        }
    }
    if (answer == 0){
        answer = -1;
    }
        
    return answer;
}

(2) Python

from collections import deque
 
def solution(maps):
    answer = 0
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    height = len(maps)
    width = len(maps[0])
    visited = [[1] * (width) for _ in range(height)]
    
    q = deque()
    q.append([0, 0])
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < height and 0 <= ny < width and visited[nx][ny] == 1 and maps[nx][ny] == 1:
                visited[nx][ny] = visited[x][y] + 1
                q.append([nx, ny])
                
    if visited[-1][-1] == 1:
        answer = -1
    else:
        answer = visited[-1][-1]
        
    return answer