1600_김우재_말이 되고픈 원숭이.md

bfs + 차원 추가 + 제한 조건 추가

문제 | 말이 되고픈 원숭이 : https://www.acmicpc.net/problem/1600
시간 | 35분

• bfs
  • bfs 를 이용해서 최단 거리를 구하기
  • 4방향 dx,dy
  • 말 이동 hores_x, hores_y 사용
• 차원 추가
  • 차원 추가관련 문제 | 벽 부수고 이동하기 : https://www.acmicpc.net/problem/2206
    • 벽을 부술 수 있는 횟수를 주는 것이 말이 되고픈 원숭이랑 비슷하다고 생각해서 차원 추가
  • tuple 을 이용해서 한번에 계산
  • 3차원 구조는 memset 안되고 {-1, } 이 안되어서 3중 for 구문으로 -1 초기화
• 제한 추가
  • 이동 가능 횟수 존재
  • 이동 가능할 때만 말같이 이동하는 로직 실행하게함
  • 아에 못가면 -1 출력해야함
    • flag 추가해서 -1 이 아닌값이 1개라도 나오면 flase 로 해당 값 사용
    • 만약 전부 -1 이라면 99999 -> -1 로 값 변경

#include <iostream>
#include <string>
#include <queue>
#include <tuple>

using namespace std;

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

int hores_x[] = {1, -1, 2, 2, -2, -2, 1, -1};
int hores_y[] = {2, 2, 1, -1, 1, -1, -2, -2};

int main(void) {
    int k; cin >> k;
    int width, height;
    cin >> width >> height;
    vector<vector<int>> map(height, vector<int> (width, 0));
    
    for(int i=0; i < height; i++){
        for(int j=0; j < width; j++){
            cin >> map[i][j];
        }
    }
    // 왼쪽 위에서 아래로
    // 내가 봤을 때는 차원을 이용해야 할 것 같음
    int pass[31][200][200];
    for(int i=0; i < 31; i++){
        for(int j=0; j < 200; j++){
            for(int k=0; k < 200; k++){
                pass[i][j][k] = -1;
            }
        }
    }
    pass[0][0][0] = 0;
    queue<tuple<int, int ,int>> q;
    q.push(make_tuple(0,0,0));
    
    while (!q.empty()) {
        int count = get<0>(q.front());
        int now_x = get<1>(q.front());
        int now_y = get<2>(q.front());
        q.pop();
        for(int i=0; i < 4; i++){
            int nx = now_x + dx[i];
            int ny = now_y + dy[i];
            if(nx >= 0 && nx < height && ny >= 0 && ny < width && map[nx][ny] != 1){
                if(pass[count][nx][ny] == -1 || pass[count][nx][ny] > pass[count][now_x][now_y]+1){
                    pass[count][nx][ny] = pass[count][now_x][now_y]+1;
                    q.push(make_tuple(count, nx, ny));
                }
            }
        }
        if(count < k){
            for(int i=0; i < 8; i++){
                int nx = now_x + hores_x[i];
                int ny = now_y + hores_y[i];
                if(nx >= 0 && nx < height && ny >= 0 && ny < width && map[nx][ny] != 1){
                    if(pass[count+1][nx][ny] == -1 || pass[count+1][nx][ny] > pass[count][now_x][now_y]+1){
                        pass[count+1][nx][ny] = pass[count][now_x][now_y]+1;
                        q.push(make_tuple(count+1, nx, ny));
                    }
                }
            }
        }
    }
    int answer = 999999;
    bool flag = true;
    for(int i=0; i <= k; i++){
        if(pass[i][height-1][width-1] != -1){
            flag = false;
            answer = min(answer, pass[i][height-1][width-1]);
        }
    }
    if(flag) answer = -1;
    cout << answer << "\n";
    return 0;
}