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

문제 설명

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

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

프로그래머스

제한 사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

입출력 예

maps	answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

풀이

#include<vector>
#include <queue>
using namespace std;

int n, m;
vector<vector<int>> board;
queue<pair<int, int>> Q;

void bfs(vector<vector<int>> &maps){
    vector<int> dist{1, 0, -1, 0, 1};
    while(!Q.empty()){
    	int x = Q.front().first;
    	int y = Q.front().second;
    	Q.pop();
    	
        for(int i = 0; i < 4; i++){
        	int nx = x + dist[i];
        	int ny = y + dist[i+1];
        	if(nx < 0 || nx >= n || ny < 0 || ny >= m || board[nx][ny] > 0 || maps[nx][ny] == 0){
            	continue;
        	}
        	board[nx][ny] += board[x][y] + 1;
        	Q.push({nx, ny});
    	}
    }
}

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    n = maps.size();
    m = maps[0].size();
    board.resize(n+1, vector<int>(m+1, 0));
    
    Q.push({0, 0});
    bfs(maps);
   
    answer = board[n-1][m-1];
    if(answer == 0){
        return -1;
    }
    
    return answer + 1;	//(0, 0) 시작 지점은 카운트 안했기에 1더한다.
}

 

python

from collections import deque

def solution(maps):
    
    n = len(maps)
    m = len(maps[0])
    
    board = [[0]*m for _ in range(n)]
    
    board[0][0] = 1
    board[n-1][m-1] = -1
    
    queue = deque([(0, 0)])
    
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    while queue:
        row, col = queue.popleft()
        for i in range(4):
            nr = row + dy[i]
            nc = col + dx[i]
            if nr < 0 or nc < 0 or nr >= n or nc >= m:
                continue
            if maps[nr][nc] == 0:
                continue
            if board[nr][nc] > 0:
                continue
            
            board[nr][nc] = board[row][col] + 1
            queue.append((nr, nc))
            
    return board[n-1][m-1]