[프로그래머스] 게임 맵 최단거리 / BFS, DFS, Queue

문제

 

 

풀이 1. (DFS)

#include<vector>
#include<string.h> // memset
using namespace std;

bool visited[100][100];
int dx[4];
int dy[4];
int N, M, min_count = 10000;
bool enable = false;
vector<vector <int>> map;

/*********************************
dfs로 구현 버전
테스트 케이스는 전부 통과하였으나
효율성을 통과하지 못함
*********************************/

void dfs(int y, int x, int count){
    count++;
    if(y == N-1 && x == M-1){
        if(count < min_count) min_count = count;
        enable = true;
        return;
    }
    
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(ny >= 0 && nx >= 0 && ny < N && nx < M){
            if(map[ny][nx]){ // 1(길)이라면..
                map[y][x] = 0;
                dfs(ny, nx, count);
                map[y][x] = 1;
            }
        }
    }
    
}

int solution(vector<vector<int> > maps)
{
    
    map = maps;
    min_count = 10000;
    enable = false;
    
    dx[0] = 1; dx[1] = 0; dx[2] = -1; dx[3] = 0;
    dy[0] = 0; dy[1] = 1; dy[2] = 0; dy[3] = -1;
    
    int answer = 0;
    
    N = maps.size();
    M = maps[0].size();
    
    // 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 
    // 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치
    
    dfs(0,0,0);
    
    if(enable) answer = min_count;
    else return -1;
    
    return answer;
    
}

 

너비 우선 탐색 dfs로 구현 버전이다.
테스트 케이스는 전부 통과하였으나 효율성을 통과하지 못했다.

따라서 최단거리를 구할 때 유용한 깊이 우선 탐색(BFS)을 활용해 다시 코드를 구현했다.

 

 

 

풀이 2 (BFS)

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

int dx[4];
int dy[4];
int N, M;
queue<pair<int,int>> q;
vector<vector<int>> count;
vector<vector<int>> map;
//dfs -> bfs((너비우선 탐색)
//dfs(깊이우선탐색)은 모든 노드를 탐색할때
//bfs(너비우선탐색)은 최단 거리를 탐색할때
//bfs는 자료구조 Queue사용

int solution(vector<vector<int> > maps)
{
    map = maps;
    int answer = 0;
    N = maps.size();
    M = maps[0].size();
    count.assign(N,vector <int>(M,0)); // 맵 위치마다 현재 count를 새기면서 지나감.
    
    dx[0] = 1; dx[1] = 0; dx[2] = -1; dx[3] = 0;
    dy[0] = 0; dy[1] = 1; dy[2] = 0; dy[3] = -1;

    //bfs
    q.push(pair(0,0));
    count[0][0] = 1;
    pair<int, int>  po;
    while(!q.empty()){
        po = q.front();
        map[po.first][po.second] = 0; // 이미 지나온 길 0
        q.pop();
        for(int i=0; i<4; i++){
            int ny = po.first + dy[i];
            int nx = po.second + dx[i];
            if(ny >= 0 && nx >= 0 && ny < N && nx < M){
                if(map[ny][nx] == 1){
                    map[ny][nx] = 0;
                    count[ny][nx] = count[po.first][po.second] + 1;
                    q.push(pair(ny,nx));
                }
            }
        }
    }
    
    
    if(count[N-1][M-1]!=0) answer = count[N-1][M-1];
    else return -1;
    return answer;
    
}

BFS를 활용한 풀이이다.

최단거리를 구할 때는 깊이를 끝까지 탐색하는 깊이 우선 탐색(DFS)보다 너비 우선 탐색(BFS)이 효율성이 좋다.

 

BFS를 활용해야만 효율성 테스트가 통과되는 이유

• DFS는 해당 노드의 자식 노드들을 모두 탐색한 후 형제 노드를 탐색한다.
• 최악의 경우 DSF는 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해에 도달하는 데 가장 오랜 시간이 걸린다.
  
  
• BFS는 시작점에 인접한 모든 정점들을 우선 방문하는 한 후, 탐색한 정점들에서 인접한 모든 정점들을 방문한다.
• BFS는 DFS과는 다르게 무작정 막힐때까지 탐색을 진행하지 않고, 이곳저곳 살펴보면서 탐색을 진행
• BFS는 출발노드에서 목표 노드까지의 최단 길이 경로를 보장한다.

 

 

 

---

 

다른 사람 풀이

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

using namespace std;

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

int solution(vector<vector<int> > maps)
{
    int n, m;
    n = maps.size();
    m = maps[0].size();
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    check[0][0] = true;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0<=nx && nx<n && 0<=ny && ny<m){
                if(check[nx][ny] == false && maps[nx][ny] > 0){
                    check[nx][ny] = true;
                    maps[nx][ny] = maps[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }



    int answer = 0;
    if(maps[n-1][m-1] == 1){
        answer = -1;
    }else{
        answer = maps[n-1][m-1];
    }
    return answer;
}

나와 다른 점이 있다면 따로 bool타입의 배열(check)을 만들어 이미 지나간 길인지 아닌지 확인했다는 점!

나는 map에 직접 1과 0을 넣어 확인했다.

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges