[백준] 미로 탈출

이제는 꽤 익숙해진 문제 유형이라 생각하고 실제로 내 블로그에 꽤 많이 적은거같다. 마술로 벽을 한번 무시하고 지나갈 수 있는 조건에 BFS 였다.

이렇게 움직이는 조건에서 최소값을 구하는 경로를 다르게 생각해줘야할때는 뭐다? 3차원 visited 벡터를 사용해줘야한다.

다만 이 전에 썼던 방식과는 살짝 다르게 코드를 작성해주었고 조금 더 깔끔해진거는 있다. 여기서 중요한 점은, 이 코드의 목적은 어느 한 지점에 도달 하기만 하면은 되는 조건이기에 BFS로 모든 조건을 넣어도 된다. 하지만 만약에 가장 길거나, 어떤 형식의 조합을 만드는 문제면은 DFS 를 쓰는게 맞다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N, M, Hx, Hy, Ex, Ey;
int matrix[1001][1001]; 
bool visited[1001][1001][2]; 
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; 

struct Hong{
    int x, y, dist, magic; 
};

void Input(){
    cin >> N >> M >> Hx >> Hy >> Ex >> Ey;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> matrix[i][j]; 
        }
    }
}

void Solution(){
    memset(visited,false,sizeof(visited)); 
    Hx--, Hy--; 
    int answer = -1; 
    queue<Hong> q; 
    q.push({Hx,Hy,0,1}); 
    visited[Hx][Hy][0] = true;
    visited[Hx][Hy][1] = true; 

    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            Hong first = q.front();
            q.pop(); 

            int x = first.x, y = first.y, dist = first.dist, magic = first.magic; 

            if(x == Ex-1 && y == Ey-1){
                cout << dist;
                return; 
            }


            for(pair<int,int>& p : dir){
                int nX = x + p.first;
                int nY = y + p.second;

                if(nX < 0 || nY < 0 || nX >= N || nY >= M || magic == 0 && matrix[nX][nY] == 1) continue; 

                if(matrix[nX][nY] == 1){
                    if(!visited[nX][nY][magic-1]){
                        q.push({nX,nY,dist+1,magic-1}); 
                        visited[nX][nY][magic-1] = true; 
                    }
                }

                if(matrix[nX][nY] == 0){
                    if(!visited[nX][nY][magic]){
                        q.push({nX,nY,dist+1,magic}); 
                        visited[nX][nY][magic] = true; 
                    }
                }
            }
        }
    }

    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

배운점:
1. 3차원 벡터 사용하기
2. DFS 와 BFS의 차이점