🐣 문제

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

---

🐤 풀이

1. queue에 처음 위치를 담아주고, 처음 위치의 거리를 1로 설정한다.
2. queue가 empty가 될 때 까지,
   2.1 동서남북으로 움직이며 새로운 좌표를 찾아,
   2.2 방문하지 않았고, 1인 곳을 찾는다.
   2.3 거리를 이전 거리 + 1로 변경해주고,
   2.4 다시 queue에 담는다.
3. 맨 끝 좌표에 저장된 거리를 리턴한다.

• 상하좌우로 움직이는 코드

int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

• 좌표가 유효한 곳을 가리키는지 확인하는 코드

if(nx >= 0 && nx < maps[0].size() && ny >= 0 && ny < maps.size())

• 2차원 배열 dist를 -1로 초기화 해, 방문 여부 확인과 거리 저장을 함께 해주었다.

int dist[101][101];
memset(dist, -1, sizeof(dist));

---

🐥 코드

#include<vector>
#include<queue>
#include<iostream> 
#include<cstring>

using namespace std;

int dist[101][101];

int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

int solution(vector<vector<int> > maps){
    
    memset(dist, -1, sizeof(dist));
    
    queue<pair<int, int>> q;
    q.push({0,0});
    dist[0][0] = 1;
    
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if(nx >= 0 && nx < maps[0].size() && ny >= 0 && ny < maps.size()){
                if(dist[ny][nx] == -1 && maps[ny][nx] == 1){
                    dist[ny][nx] = dist[y][x] + 1;
                    q.push({ny, nx});
                }
            }
        }
    }
    
    return dist[maps.size()-1][maps[0].size()-1];
}