[C++][Programmers][DFS/BFS] 게임 맵 최단거리

문제

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

프로그래머스

 

해결법

BFS 기본/대표 문제다. 최단거리 찾기 문제이므로 Queue를 이용한 BFS 탐색을 진행하면 된다.

이 때, 구지 방문체크 배열을 안만들고 현재 값에 +1을 하며 값을 변경해주면 더 편하게 구현 가능하다.

 

 

알아둘 것

1) BFS 코드

#include <vector>
#include <queue>
#include <utility>//pair queue
using namespace std;

int BFS(vector<vector<int>> maps){
    int direction[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};//상하좌우 방향키
    queue<pair<int, int>> q;//BFS 탐색을 위한 queue
    
    //현재 좌표 queue에 추가
    q.push(make_pair(0,0));
    
    //queue가 빌 때까지 탐색
    while(!q.empty()){
    
    	//현재 queue 빼기 전에 값 변수에 저장해두기
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        //주변 탐색. 대부분 상하좌우 탐색.
        for(int k = 0; k < 4; k++){
            int nx = x + direction[k][0];
            int ny = y + direction[k][1];
            
            //이동 가능한 곳이면 해당좌표를 queue에 넣기
            if(maps[nx][ny] == 1){
                maps[nx][ny] = maps[x][y] + 1;
                q.push(make_pair(nx,ny));
            }
        } 
     }
}

2) pair queue, queue 사용법

#include <queue>
#include <utility>//pair queue를 위해 선언

//queue 선언. 인자 2개 넣을거면 pair queue로 생성
queue<pair<int, int>> q;

//q에 pair값 넣기
q.push(make_pair(0,0));

//q의 첫번째 원소 x, y값 꺼내기
int x = q.front().first;
int y = q.front().second;

//q 맨 앞 값 꺼내기
q.pop();

 

코드

#include <vector>
#include <queue>
#include <utility>//pair queue
using namespace std;

int BFS(vector<vector<int>> maps){
    int direction[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};//상하좌우 방향키
    queue<pair<int, int>> q;//BFS 탐색을 위한 queue
    
    //0,0 부터 탐색 시작
    q.push(make_pair(0,0));
    
    //queue가 빌 때까지 탐색
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        //상하좌우 탐색
        for(int k = 0; k < 4; k++){
            int nx = x + direction[k][0];
            int ny = y + direction[k][1];
            //범위체크
            if(nx < 0 || nx >= maps.size() || ny < 0 || ny >= maps[0].size()) continue;
            //상대팀 진영에 도착했다면 바로 정답 리턴. 효율성 테스트를 위해.
            if(nx == maps.size()-1 && ny == maps[0].size()-1) return maps[x][y] + 1;
            //가는 길이 1이면 탐색 queue에 추가
            if(maps[nx][ny] == 1){
                maps[nx][ny] = maps[x][y] + 1;
                q.push(make_pair(nx,ny));
            }
        }
        //현재 값에 + 1 한 값을 이웃 블럭에 넣어야 하므로 map[0][0] = 2 로 맞춰두기.
        if(x == 0 && y == 0)  maps[x][y] = 2;
    }
    //queue가 빌 때 까지 탐색했는데 상대팀 진영을 못만났다면 갈 수 없는 것. return -1.
    return -1;
}

int solution(vector<vector<int>> maps){
    return BFS(maps);
}