❓문제 설명

문제: 프로그래머스 게임 맵 최단거리

난이도: Level 2

🎯문제 해결 방법

이 문제는 간단한 BFS 문제입니다. 다만, 효율성 테스트에서 조건을 모두 처리해주지 않으면 시간초과가 발생해서 정답처리가 되지 않습니다.

bool vst[104][104]; // 방문여부
int dist[104][104]; // 거리
int dx[4] = {1,-1,0,0}; // 방향
int dy[4] = {0,0,1,-1}; // 방향
queue<pair<int,int>> q; // BFS를 위한 Queue

int ns = m.size();
int ms = m[0].size();
memset(dist, -1, sizeof(dist));

편의성을 위해 vector<vector<int>> m를 매개변수로 받는 solution 함수에서 가로, 세로 길이를 먼저 변수에 저장해주고 dist 배열을 -1로 초기화 해줍니다.

	q.push({0,0});
    vst[0][0] = 1;
    dist[0][0] = 1;
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        if(cur.first == ns - 1 && cur.second == ms - 1) {
            return dist[ns-1][ms-1];
        }
        for(int dir=0; dir<4; dir++){
            int nx = cur.second + dx[dir];
            int ny = cur.first + dy[dir];
            if(nx < 0 || ny < 0 || nx >= ms || ny >= ns) continue;
            if(vst[ny][nx] || m[ny][nx] == 0 || dist[ny][nx] != -1) continue;
            q.push({ny,nx});
            vst[ny][nx];
            dist[ny][nx] = dist[cur.first][cur.second] + 1;
        }
	}

(1,1) 부터 시작해서 (n,m)까지 가는 최단 거리를 구하는 것이기 때문에 (1,1)에 해당하는 (0,0)을 큐에 넣어주고 (n-1, m-1)까지 가기 위한 while 문으로 BFS를 돌게 됩니다.

이때 저는 if(vst[ny][nx] || m[ny][nx] == 0 || dist[ny][nx] != -1) continue; 코드에서 dist[ny][nx] != -1 처리를 해주지 않아서 시간초과가 났었습니다. vst[ny][nx]로 이미 방문한 곳이 처리가 될 것이라고 생각되었는데 그렇지 않았습니다.

💻전체 코드

#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

bool vst[104][104];
int dist[104][104];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
queue<pair<int,int>> q;

int solution(vector<vector<int>> m)
{
    int ans = 0;
    int ns = m.size();
    int ms = m[0].size();
    memset(dist, -1, sizeof(dist));
    q.push({0,0});
    vst[0][0] = 1;
    dist[0][0] = 1;
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        if(cur.first == ns - 1 && cur.second == ms - 1) {
            return dist[ns-1][ms-1];
        }
        for(int dir=0; dir<4; dir++){
            int nx = cur.second + dx[dir];
            int ny = cur.first + dy[dir];
            if(nx < 0 || ny < 0 || nx >= ms || ny >= ns) continue;
            if(vst[ny][nx] || m[ny][nx] == 0 || dist[ny][nx] != -1) continue;
            q.push({ny,nx});
            vst[ny][nx];
            dist[ny][nx] = dist[cur.first][cur.second] + 1;
        }
    }
    if(dist[ns-1][ms-1] == -1) ans = -1;
    else ans = dist[ns-1][ms-1];
    return ans;
}