[백준 2206] - 벽 부수고 이동하기(C++)

📕문제

---

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

📕입력

---

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

📕출력

---

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

🔎문제 해석

---

 

문제는 굉장히 간단하다.

(1.1)에서 (N, M)까지 갈 수 있는 최단경로를 구하는 것이다.

근데 여기서 중요한 점은 벽을 언제 뚫을 것인가가 중요하다.

벽은 딱 한번 뚫을수 있다.

 

💡초기 풀이 방식

---

1. graph 배열 : 입력받은 행렬 [0은 이동가능, 1은 벽], visit 배열 : 여기까지 도달하는데 거쳐간 칸의 개수를 저장
2. 출발점인 (1,1)을 queue에 푸쉬하고 visit[1][1]에 1을 저장
3. BFS진행
   1. queue에서 좌표를 추출해서, 상하좌우로 이동한다.
      • 이동하는 좌표가 적절하지 않다면 이동x [배열을 벗어난 좌표]
      • 이동하려는 좌표가 적절하다면
        1. graph값이 0인지, visit값이 0인지를 체크함.
           • 적절하다면 queue에 푸쉬하고, visit값을 visit(출발좌표)+1로 갱신해줌.
        2. 만약 graph값이 1이라면, 또 다른 bfs를 출력 (벽을 뚫은 경우)
           • 이 bfs는 1을 만나면 절대로 push 하지 않고 0으로만 이동함.
           • 최종 도착점에 도착하면 그때의 visit값을 return 해서 최소값과 비교함.
           • 만약 도착점에 도착했다면 bool arrive 값을 true로 바꿈.
4. BFS함수를 나온 뒤에 arrive 값이 false 라면 도착하지 못했다는 뜻이므로 -1을 출력
5. BFS함수를 나온 뒤에 ariive 값이 true라면 그 때의 최소값을 출력했음.

🛑문제점

---

1. 코드를 제출한 결과 시간초과가 나왔음. 
   1. 아마 BFS 내부에서 또 다른 BFS를 출력해서 시간초과가 난듯.
2. 벽을 아예 안 뚫고 가는 경우를 생각안해줬음. 
   1. 최소 한번은 벽을 뚫고 간다는 가정을 해서 또 다른 테케에서 결과값이 달라서 실패한듯.

👀해결방안

---

1. 또 다른 BFS를 출력하지 않기 위해서는 벽을 부쉈다는 여부를 변수로 저장해줘야함.
   1. visit배열과 queue에다가 벽을 부쉈는지에 대한 내용을 저장.
2. visit배열을 2차원배열이 아닌 3차원 배열로 생성해서 벽을 부쉈는지에 대한 여부를 저장해주기로 했음.

💡수정 풀이 방식

---

1. graph[a][b] 배열 : 입력받은 행렬 , visit[a][b][c] : a = row, b = col , c = block여부(벽부숨[0], 벽안부숨[1])\
2. queue : {(row,col),block여부)}
3. 초기값 : visit[1][1][1]=1, queue[(1,1),1] 설정
4. BFS함수 실행
   • q에 있는 값들을 추출함.
   • 추출한 좌표가 도착점의 좌표와 일치하는지 검사
     • 일치하면 좌표에 해당하는 visit배열 값을 return함.
     • 일치하지 않으면 BFS함수 그대로 진행
   • 4방향에 대해서 갈 수 있는 이동좌표를 검사
     • 적절하지 않는 이동 [ 배열을 넘어가는 경우]  pass
     • 이동하려는 좌표의 graph값이 0이고, 한번도 방문하지 않은 경우
       • queue에 row,col,block값을 그대로 푸시하고 visit값도 이동하기전 좌표 값에 +1 해줌.
     • 만약 block이 1이고[벽을 아직 부수지 않았고], graph값이 1이라면
       • queue에다가 row,col,0을 푸쉬하고, visit값도 이동하기전 좌표 값에 +1해줌
         • 여기서 위의 과정과 차이점은 visit값에 block값을 0으로 해줌.
           • 벽을 뚫었다는 표시를 해줘야함. 그래야 다음에 뚫지 않음.

 

💻코드

/*
2206 골드3 벽부수고 이동하기
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n, m;
vector<vector<int>> graph;
vector<vector<vector<int>>> visit; //3차원 배열
queue<pair<pair<int, int>,int>> q;
vector<int> x = {-1, 1, 0, 0};
vector<int> y = {0, 0, -1, 1};
int bfs();
int main()
{
    cin >> n >> m;
    graph.resize(n + 1, vector<int>(m + 1, 0));
    visit.resize(n + 1, vector<vector<int>>(m + 1,vector<int>(2,0)));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%1d", &graph[i][j]);
        }
    }
    q.push(make_pair(make_pair(1, 1),1)); //초기 출발점을 넣습니다.
    visit[1][1][1] = 1;         //방문 처리
    cout<<bfs();
}
int bfs()
{
    //갈 수 있는 모든 방향을 넣어볼까?
    while (!q.empty())
    {
        int tempx = q.front().first.first;
        int tempy = q.front().first.second;
        int block=q.front().second;
        if(tempx==n && tempy==m){ //도착하면 그때의 거쳐간 벽의 개수를 return 해줌.
            return visit[tempx][tempy][block];
        }
        q.pop();
        // q에 있는 좌표를 추출.
        for (int i = 0; i < 4; i++)
        {
            int fx = tempx + x[i];
            int fy = tempy + y[i];
            if (fx <= 0 || fx > n || fy <= 0 || fy > m)
            { //이동할려는 좌표가 배열을 벗어날때
                continue;
            }
            
            if (graph[fx][fy] == 0 && visit[fx][fy][block] == 0) //이동할 수 있고, 아직 방문을 안한곳이면?
            { //일단 갈 수 있다면 그 좌표는 모두 q에 넣기
                q.push(make_pair(make_pair(fx,fy),block));
                visit[fx][fy][block] = visit[tempx][tempy][block] + 1;
            }
            if (block==1 && graph[fx][fy] == 1) // block 0이면 나는 이미 벽을 뚫었다. 1이면 벽을 안뚫었다.
            { //아직 벽을 깨지 않았고, 이동하려는 좌표가 벽이라면
                q.push(make_pair(make_pair(fx, fy),0));
                visit[fx][fy][0] = visit[tempx][tempy][block] + 1;        
            }
        }
    }
    return -1;
}

 

✔느낀점

• 3차원 배열로 접근해서 벽을 뚫었다는 여부를 저장하는 것이 엄청나게 신선했다.
• 하다가 막혀서 구글을 살짝 참고했다.. ㅎㅎ,, 
• 3차원 배열을 쓰는 경우를 이제 완전히 터득한 듯?