-
[프로그래머스] 게임 맵 최단거리 c++, pythonCoding Test/programmers 2023. 2. 17. 19:07728x90
문제 설명
게임 맵의 상태 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]
728x90'Coding Test > programmers' 카테고리의 다른 글
[프로그래머스] 대충 만든 자판 c++ (0) 2023.03.06 [프로그래머스] 미로 탈출 c++ (0) 2023.02.21 [프로그래머스] 카드 뭉치 c++ (0) 2023.02.16 [프로그래머스] 둘만의 암호 c++ (0) 2023.02.11 [프로그래머스] 괄호 회전하기 c++ (0) 2023.01.30 - maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.