[Programmers] 게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=python3

프로그래머스

 

1. Python

from collections import deque
def solution(maps):
    m, n = len(maps), len(maps[0])
    q = deque()
    q.append((1, 0, 0))
    visited = set()
    visited.add((0, 0))
    dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
    while q:
        t, y, x = q.popleft()
        if y == m - 1 and x == n - 1:
            return t
        for d in range(4):
            ny, nx = y + dy[d], x + dx[d]
            if ny < 0 or ny >= m or nx < 0 or nx >= n:
                continue
            if maps[ny][nx] == 1 and (ny, nx) not in visited:
                q.append((t + 1, ny, nx))
                visited.add((ny, nx))
    return -1

 

2. C++ 

int solution(vector<vector<int>> maps)
{
	int m = maps.size();
	int n = maps[0].size();
	
	deque<vector<int>> q;
	q.push_back({1, 0, 0});
	
	set<vector<int>> visited;
	visited.insert({0, 0});
	
	int dy[4] {0, 1, 0, -1};
	int dx[4] {1, 0, -1, 0};
	
	while (not q.empty()) {
		vector<int> tmp = q.front();
		int t = tmp[0];
		int y = tmp[1];
		int x = tmp[2];
		q.pop_front();
		if (y == m - 1 and x == n - 1) {
			return t;
		}
		for (int d=0; d<4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (ny < 0 or ny >= m or nx < 0 or nx >= n) continue;
			if (maps[ny][nx] == 0) continue;
			if (visited.find({ny, nx}) == visited.end()) {
				q.push_back({t+1, ny, nx});
				visited.insert({ny, nx});
			}
		}
	}
	return -1;
}