11) 프로그래머스 Lv2 - 게임 맵 최단거리

코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

BFS로 풀었다.

잔실수가 너무 많았었던 문제

#include<bits/stdc++.h>

using namespace std;

int pos_x[4] = {0, 1, 0, -1};
int pos_y[4] = {1, 0, -1, 0};
int check[101][101] = {0,};

int solution(vector<vector<int> > maps)
{
    int n = maps.size();
    int m = maps[0].size();
    int answer = 0;
    int q_x, q_y;
    queue<pair<int, int> > q;
    
    q.push(make_pair(0, 0));
    check[0][0] = 1;
    
    int q_size = q.size();
    answer++;
    
    while(!q.empty()) {
        if(q_size <= 0) {
            q_size = q.size();
            answer++;
        }
        q_x = q.front().first;
        q_y = q.front().second;
        if(q_x == n-1 && q_y == m-1) {
            break;
        }
        q.pop();
        for(int i = 0; i < 4; i++) {
            int dx = q_x+pos_x[i];
            int dy = q_y+pos_y[i];
            if(dx >= 0 && dx < n && dy >= 0 && dy < m) {
                if(check[dx][dy] == 0 && maps[dx][dy] == 1) {
                   q.push(make_pair(dx, dy));
                   check[dx][dy] = 1;
                }
            }
        }
        q_size--;
    }
    if(q_x != n-1 || q_y != m-1) {
        answer = -1;
    }
    
    return answer;
}

잔실수 List

1. 문제를 똑바로 안읽어서 5X5로 문제를 풀었음 : d_x, d_y == 4 일때 break로 해버림

2. check 크기를 5X5로 고정함

3.아래 처럼 작성하고 왜 계속 세그폴트가 생기는지 몰랐음.

dx >= 0 && dy < n && dx >= 0 && dy < m

결론

으이구 인간아ᕙ( ︡’︡益’︠)ง