[백준][C++] 17836 공주님을 구해라!

www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

 

 

 

알고리즘 종류

    - BFS

 

 

 

사고 과정

    - 경우는 2가지이다. 

        1. 검 없이 공주님에게 달려간다. (1, 1)에서 시작해서 (n, m)에 도착하는 BFS.

        2. 검을 찾고 공주님에게 달려간다. (1, 1)에서 (sword_y, sword_x) 검이 있는 곳에 갔다가 (n, m)에 도착하는 BFS

 

    - 두 가지 경우에서 나온 시간 중에 최소 값이 제한된 시간 이하인지 확인해서 결과를 출력한다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define MAX 987654321;
 
using namespace std;
 
int n, m, t;
int sword_y, sword_x;
 
int mat[101][101];
int isVisited[101][101];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
 
bool isValid(int y, int x){
    return (y>=1 && y<=n) && (x>=1 && x<=m);
}
 
 
int bfs(int sy, int sx, int ey, int ex, bool hasSword){
    memset(isVisited, 0, sizeof(isVisited));
    queue<pair<int, int> > q;
    q.push({sy, sx});
    isVisited[sy][sx] = 1;
    
    int time = 0;
    while(!q.empty()){
        
        int size = q.size();
        while(size--){
            
            int cy = q.front().first;
            int cx = q.front().second;
            q.pop();
            
            if(cy==ey && cx==ex) return time;
            
            for(int d=0; d<4; d++){
                int ny = cy + dir[d][0];
                int nx = cx + dir[d][1];
                
                if(isVisited[ny][nx]) continue;
                if(!isValid(ny, nx)) continue;
                // 검이 있으면 그냥 뚫고 가고, 검이 없으면 벽을 검사한다. 
                if(!hasSword)
                    if(mat[ny][nx] == 1) continue;
 
                isVisited[ny][nx] = 1;
                q.push({ny, nx});
            }
        }
        
        time++;
    }
    
    return MAX; 
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m >> t;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> mat[i][j];
            if(mat[i][j] == 2) {
                sword_y = i;
                sword_x = j;
            }
        }
    }
    
    // 검 없이 구하자
    int timeNoSword = bfs(1, 1, n, m, false);
    // 검 가지고 구하자
    int timeWithSword = bfs(1, 1, sword_y, sword_x, false);
    timeWithSword += bfs(sword_y, sword_x, n, m, true);
    
    int shortTime = min(timeNoSword, timeWithSword);
    
    if(shortTime > t) cout << "Fail" << endl;
    else cout << shortTime;
}
 

 

 

 

시행착오

    - 함수 1개에 bool 자료형으로 켰다가 끄는 조건을 한 번 추가해 보았다.