[C++] 프로그래머스 Level 2 : 게임 맵 최단거리

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

using namespace std;

int answer = 0;
int N, M;

struct INFO {
    int x, y;
    int cnt;
};

bool visited[101][101] = {false}; // 방문여부 체크
queue<INFO> q;

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

void BFS(vector<vector<int> > board){
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        q.pop(); // pop 빼먹지 말 것!!!
        
        if(x == N-1 && y == M-1){
            answer = cnt;
            return;
        }
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 범위 벗어난 경우 체크 잊지 말기, 0이 벽
            if(nx < 0 || nx >= N || ny < 0 || ny >= M || board[nx][ny] == 0){
                continue;
            }
            
            if(!visited[nx][ny]){
                visited[nx][ny] = true;
                q.push({nx, ny, cnt+1});
                // visited[nx][ny] = false; - 이게 왜 시간초과?
            }
        }
    }
    // 상대방 진영에 도착하지 못할 때
    answer = -1;
}

int solution(vector<vector<int> > maps)
{
    N = maps.size();
    M = maps[0].size();
    
    q.push({0, 0, 1});
    visited[0][0] = true;
    BFS(maps);
    
    return answer;
}

BFS 연습용 문제, 시간 초과 때문에 꽤 고생했다. 단 한 줄 때문인지를 모르고

• visited를 다시 false로 초기화해 주니까 상대팀 진영에 도달하지 못하는 경우 무한루프에 빠지게 되어 시간 초과가 발생했다. 계속 갔던 길을 왔다갔다 해버리기... visitied 초기화하는 경우는 잘 생각해보아야 할 것 같다.

• 2차원 vector를 매개변수로 넘기는 방법은 vector<vector > 이렇게 해당 벡터의 자료형을 그대로 써주면 된다.