[프로그래머스] Level 2. 리코쳇 로봇

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

프로그래머스

 

해결방법

BFS 로 풀었다. 

1. 거리정보를 저장하는 2차배열을 distmap을 생성한 뒤, 모두 INT_MAX로 설정한다. 
2. 시작지점을 찾아 distmap[sx][sy] = 0으로 설정하고, queue에 집어넣는다. queue는 검사가 필요한 목록이다.
3. queue에서 한개씩 빼면서 상,하,좌,우 로 움직임을 시도한다. 
4. 맵 밖으로 벗어나서 움직일 수 업거나, i,j로 이동했는데 이 거리가 기존에 있는 distmap[i][j] 보다 크다면 비효율적인 이동을 했다는 의미이므로 queue에 집어넣지 않고 넘어간다.
5. queue가 텅 빌때까지 계속 반복한다.
6. 처음에 찾아놓았던 골인지점 (ex,ey) 에 대해 distmap[ex][ey]가 정답이다. 만약 distmap[ex][ey] == INT_MAX 라면, 도달할 수 없다는  의미이므로 -1을 리턴한다.

#include <string>
#include <vector>
#include <climits>
#include <iostream>
#include <queue>
using namespace std;


vector<int> xs =  {-1,1,0,0}; //위아왼오
vector<int> ys = {0,0,-1,1};
vector<string> _board;

pair<int,int> move(int x, int y , int dirx, int diry){
    
    while(true){
        
        //check boundary
        if(x+dirx <0 || x+dirx >= _board.size() || y+diry <0 || y+diry >= _board[0].size()) break;
        //check wall
        if(_board[x+dirx][y+diry] == 'D') break;
       
        x += dirx;
        y += diry;
    }
    
    return  make_pair(x,y);
}

int solution(vector<string> board) {
   
    _board = board;
    vector<vector<int>> distmap(board.size(),vector<int>(board[0].size(),INT_MAX));
    queue<pair<int,int>> q;
    
    int ex = 0, ey = 0;
    for(int i=0; i<board.size(); i++){
        for(int j=0; j<board[i].size(); j++){
            if(board[i][j] == 'R') {
                q.push(make_pair(i,j));
                distmap[i][j] = 0;
            }else if(board[i][j]== 'G'){
                ex = i; ey = j;
            }
        }
    }
    
    
    while(!q.empty()){
        pair<int,int> spot  = q.front();
        q.pop();
        
        int crr_dist = distmap[spot.first][spot.second];
        for(int i=0; i<xs.size(); i++){ //모든방향으로 가봄. 이전에 온 방향은 안감.
            
            pair<int,int> after = move(spot.first,spot.second ,xs[i],ys[i]); //움직여봄.
            if(after.first == spot.first && after.second == spot.second) continue; //못움직임.
            if(distmap[after.first][after.second]<= crr_dist+1) continue; //비효율이동
            //거리갱신 및 queue에 넣음.
            distmap[after.first][after.second] = crr_dist+1;
            q.push(after);
            
        }
        
    }
        
    
    int answer = distmap[ex][ey];
    return answer == INT_MAX ? -1 : answer;
}

 

 

---

 

실패코드(27개 중 9개 시간초과)

DFS로 풀었다.

처음에 실패했던 코드. 현재 지점에서부터 상하좌우로 움직여보되, 이전에 움직였던 방향으로 되돌아가지 못하도록 했다. 

visited 를 두어 이미 방문한 곳이라면 더이상 검사하지 않도록 처리했다.

#include <string>
#include <vector>
#include <climits>
#include <iostream>
using namespace std;


vector<int> xs =  {-1,1,0,0}; //위아왼오
vector<int> ys = {0,0,-1,1};
vector<string> _board;
int answer = INT_MAX;

pair<int,int> move(int x, int y , int dirx, int diry){
    
    while(true){
        
        //check boundary
        if(x+dirx <0 || x+dirx >= _board.size() || y+diry <0 || y+diry >= _board[0].size()) break;
        
        if(_board[x+dirx][y+diry] == 'D') break;
       
        x += dirx;
        y += diry;
    }
    
    return  make_pair(x,y);
}
void dfs(int x, int y, int dist, vector<vector<bool>> visited, int exceptIdx){
    
    
    if(answer != INT_MAX && dist>=answer) return;
    if(visited[x][y]) return;
    visited[x][y] = true; //이미왔던곳이라면
    
    for(int i=0; i<xs.size(); i++){ //모든방향으로 가봄. 이전에 온 방향은 안감.
        if( i == exceptIdx) continue; 
        pair<int,int> after = move(x,y,xs[i],ys[i]); //움직여봄.
        
        if(after.first == x && after.second ==y) continue; //움직이지 못했음.
        //목적지  도달
        if(_board[after.first][after.second] =='G'){
            answer = min(answer,dist+1);
            return;
        } 
        
        dfs(after.first, after.second, dist+1, visited, i%2==0? i+1 : i-1);
    }
    
}

int solution(vector<string> board) {
   
    _board = board;
    vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(),false));
    for(int i=0; i<board.size(); i++){
        for(int j=0; j<board[i].size(); j++){
            if(board[i][j] == 'R') {
                dfs(i,j,0,visited,-1);
                break;
            }
        }
    }
    
    return answer == INT_MAX ? -1 : answer;
}

 

 

 

 

결론 및 비교

코드알고리즘최악의 시간 복잡도는 아래와 같다.

1번 코드 (BFS)	BFS	O(NM(N+M))O(NM(N+M))O(NM(N+M))
2번 코드 (DFS)	DFS + 백트래킹	O(4NM)O(4^{NM})O(4NM) (최악), 현실적으론 O(NM(N+M))O(NM(N+M))O(NM(N+M))

 

 항상 BFS와 DFS는 어떤것을 선택할지 고민되는 문제이다. 

 

BFS 가 효율적인 경우

1. 최단거리를  찾는 문제에서는 일반적으로 BFS가 효율적이라고 한다. BFS는 모든 경로를 같은 깊이에서 먼저 탐색하기 때문에, 특정 지점까지의 최단거리를 찾는데 용이하다.
2. 모든 간선의 가중치가  같을때(그래프) . 체스판에서 말의 최소 이동횟수를 찾는 경우가 예가 될 수 있다.
3. detph 단위로 탐색해야할 때. SNS에서 특정 사용자와 특정 단계 이내의 친구를 찾는 경우, 트리에서 레벨별로 노드를 방문하는 경우이다.

DFS가 효율적인 경우

1. 모든 경우의 수를 찾아야 하는 경우. 미로에서 가능한 모든 경로를  찾는 문제, 백트래킹을 이용한 문제는 DFS를 사용한다.
2. 그래프가 순환하는지를 체크하는 경우.

 

BFS vs DFS 정리

문제 유형BFS (큐 사용)DFS (스택 or 재귀 사용)

최단 거리(이동 횟수 최소화)	✅	❌
모든 경우의 수 탐색 (백트래킹)	❌	✅
경로 찾기 (가능한 모든 경로 탐색)	❌	✅
메모리 사용 (작은 경우 유리)	❌ (큐를 사용하므로 공간 많이 필요)	✅ (스택 또는 재귀로 탐색)
시간 효율성 (작은 문제에서 유리)	✅ (빠르게 탐색)	❌ (경우의 수가 많아지면 비효율적)
그래프의 사이클 찾기	❌	✅
트리 탐색	❌	✅
위상 정렬 (DAG)	❌	✅