🖊️ 문제

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

---

🖊️ 풀이

최단거리라는 것은.. BFS라는 것 .......
BFS 처음 풀어봤는데
DFS와 함께 공부하고, 첫 문제니까 검색해가면서 같이 해봤다

시작노드(0,0)부터 큐에 넣으면서 시작
루프돌면서~
queue에서 pop하고
인접 노드 중 접근 가능한 노드들을 큐에 push한다.

그리고!!
내가 어려웠던 부분은 최단거리 구하는 부분.
사실 그냥 answer++하니까 큐에 들어간 모든 노드들의 개수가 리턴되더라 (당연함ㅋㅋ)

이전에 방문했던 노드 + 1이 현재 노드까지 들어온 거리임
그래야 최종 노드에 해당하는 위치가 최단 거리가 된다.

그리고 ㅋㅋ
개쪽팔린데
정신놓고 bfs에만 집중하다가
행, 열을 바꿔서 오답나옴 ㅋㅋ
부디 정신을 차리기 바랍니다...
(왜 그랬냐면
n x m 이라고 문제에서 주어짐
그래서 n = 행 (maps[0].size())
m = 열 (maps.size())임
근데 마지막에 n과 m을 거꾸로 넣어버림 ㅋㅋ
이런.. 초딩같은 실수는 하지 말자 너무 어이없어서 찾지도 못했음 ㅋㅋ

이번에는 배우다 싶이 했으니까 아래 코드에 주석 달겟숨용

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

int solution(vector<vector<int>> maps)
{
    int answer = 0;
    queue<pair<int, int>> bfs;
	bool visited[101][101] {false};			// 방문 여부
    int dist[101][101] {-1};				// 최단거리
    
    int dx[4] {-1, 0, 1, 0};
	int dy[4] {0, -1, 0, 1};

   	int n = maps[0].size();				// 행
    int m = maps.size();				// 열
   
    bfs.push(make_pair(0,0));			// (0,0) : 시작노드
    visited[0][0] = true;
    dist[0][0] = 1;
    while(!bfs.empty()) {
        int curx = bfs.front().first;
        int cury = bfs.front().second;
        bfs.pop();					
        
        // 4방향 (동서남북) 검색
   		for(int i = 0 ;i < 4 ; i++) {	
            int nextx = curx + dx[i];
            int nexty = cury + dy[i];
            if (nextx < 0 || nextx > m-1 || nexty < 0 || nexty > n-1) continue;	//배열오버
            if (maps[nextx][nexty] == 0) continue;								//접근불가
            if (!visited[nextx][nexty]) {
                bfs.push(make_pair(nextx, nexty));
                visited[nextx][nexty] = true;
                dist[nextx][nexty] = dist[curx][cury] + 1;	//현재거리 = 이전거리+1
            }
    	}
    }
    if (!visited[m-1][n-1]) 			// bfs끝났는데 방문못했으면 도착못한거임
        answer = -1;
    else
        answer = dist[m-1][n-1];
        
    return answer;
}