[C++] 2206번 벽 부수고 이동하기 - 그래프 이론, BFS

#include <iostream>
#include <queue>

#define MAX_MAP_SIZE 1002
#define IOF 987654321

using namespace std;

typedef struct _loc {
    int x;
    int y;
    int nb_cnt;  //부수다: break, 부수지 않다: not break
    int b_cnt;
} loc;

int Dist[MAX_MAP_SIZE][MAX_MAP_SIZE][2];  //거리의 최솟값(안 부쉈나? 부쉈나?)
char Map[MAX_MAP_SIZE][MAX_MAP_SIZE];  //맵
queue<loc> q;  //bfs용 큐
int N, M;  //맵의 크기

int X_d[4] = {1, 0, -1, 0};  //X direction
int Y_d[4] = {0, -1, 0, 1};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    for(int i=0; i<=N+1; i++) {
        for(int j=0; j<=M+1; j++) {
            if(!i || !j || i>N || j>M) {  //맵의 영역을 벗어날 경우 2 넣기
                Map[i][j]='2';
                continue;
            }
            cin >> Map[i][j];
        }
    }
    
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=M; j++) {
            Dist[i][j][0]=IOF;  //맵에 최대값 넣어주기
            Dist[i][j][1]=IOF;
        }
    }
    
    q.push({1, 1, 0, 0});
    
    while(!q.empty()) {
        loc t = q.front(); q.pop();
        int change=0;
        
        if(t.nb_cnt<Dist[t.x][t.y][0]) {
            Dist[t.x][t.y][0]=t.nb_cnt;
            change=1;
        }
        if(t.b_cnt<Dist[t.x][t.y][1] && t.b_cnt) {
            Dist[t.x][t.y][1]=t.b_cnt;
            change=1;
        }
        if(!change)  //만약 값이 갱신되지 않았다면 돌아가기
            continue;
            
        for(int i=0; i<4; i++) {
            int n_x = t.x+X_d[i];  // new_x
            int n_y = t.y+Y_d[i];
            
            switch(Map[n_x][n_y]) {
                case '2':
                    continue;
                case '1':
                    if(t.b_cnt)
                        continue;  //벽을 2번 부숴야 하므로 돌아가기
                    else  //벽을 1번 부숨
                        q.push({n_x, n_y, IOF, t.nb_cnt+1});
                    break;
                case '0':
                    if(t.b_cnt)  //벽을 한 번 부쉈을 경우 b_cnt+1
                        q.push({n_x, n_y, IOF, t.b_cnt+1});
                    else  //벽을 안 부쉈으면 b_cnt=0, nb_cnt+
                        q.push({n_x, n_y, t.nb_cnt+1, 0});
            }
        }
    }
    
    if(Dist[N][M][0] == IOF && Dist[N][M][1] == IOF)
        cout << -1 <<endl;
    else {
        if(!Dist[N][M][1] || Dist[N][M][0] < Dist[N][M][1])
            cout << Dist[N][M][0]+1;  //안부순게 더 거리가 적거나, 아예 부수지 않았으면
        else
            cout << Dist[N][M][1]+1;
    }
    
    return 0;
}

 

말했지만 내 코드는 별로 좋은 코드가 아니다. 나는 배우는 입장으로써 메모용으로 작성하고 있다. 만약 모범 답안을 보고 싶다면 다른 사람이 작성한 코드가 적혀 있는 블로그가 아래에 있으니 그걸 보도록 하자.맨처음에 DFS로 풀다가 시간 초과 나서 망했다. 왜 DFS로 풀려고 햇는지 잘 모르겠다. 그리고 다시 BFS로 넘아와서 풀었는데 중요한 걸 놓친 것이 있었다. BFS로 탐색하게 되면 탐색하는 곳까지의 거리가 모두 같다.(다익스트라 처럼) 그래서 거리가 더 짧다. 를 확인할 필요가 없이 그냥 이미 왔던 곳인지만 확인하면 됬던 것이다. ㅋㅋㅋ;;...ㅠㅠ 아무튼 그렇다. 참고한 사이트는 아래에 있다.

 

 

<C++ queue>

https://life-with-coding.tistory.com/408

[C++][STL] Queue 기본 사용법 및 예제

 

<C++ 구조체 queue>

https://hydroponicglass.tistory.com/15

[C++, STL] 큐에서 구조체 사용

 

<모범 코드. 타 블로그입니다.>

https://wtg-study.tistory.com/86

[C++] 백준 2206 : 벽 부수고 이동하기

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다