문제

문제 링크

어떻게 접근할 것인가

  • 일반 BFS에서 뚫은 경험이 있는지와 길이 뚫려있는지에 따라 경우의 수를 3개로 나눴다.
  • 1.길이 뚫려있는데 아직 안가본 길인 경우
  • 2.길은 뚫려있는데 가본 길이고 아직 뚫을 수 있는 경우
  • 3.길이 막혀있는데 아직 뚫을 수 있는 경우

코드

#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

typedef struct Point{
    int x, y;
    Point(int i, int j){
        x = i;
        y = j;
    }
}Point;
int v[1010][1010] = {0,};
int d[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
int n, m, answer = 10000000;
int bfs(){
    int dist[1010][1010] = {0,};
    int drill[1010][1010] = {0,};
    queue<Point> q;
    q.push(Point(0, 0));
    dist[0][0] = 1;
    while(!q.empty()){
        Point temp = q.front(); q.pop();
        int t = dist[temp.x][temp.y];
        int dr = drill[temp.x][temp.y];
        
        for(int i = 0; i < 4; i++){
            int X = temp.x + d[i][0], Y = temp.y + d[i][1];
            if(X >= n || Y >= m || X < 0 || Y < 0) continue;
            if(v[X][Y]){
                if(!dist[X][Y]){
                    dist[X][Y] = t + 1;
                    q.push(Point(X, Y));
                    drill[X][Y] = dr;

                }
                else if(drill[X][Y] && !dr){
                    dist[X][Y] = t + 1;
                    q.push(Point(X, Y));
                    drill[X][Y] = dr;
                }
            }
            else if(!v[X][Y] && !drill[temp.x][temp.y]){
                dist[X][Y] = t + 1;
                q.push(Point(X, Y));
                drill[X][Y] = 1;
            }
            if(X == n - 1 && Y == m - 1)return dist[X][Y];
        }
    }
    return -1;
}

int main(){
    scanf("%d %d ", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char temp;
            scanf("%c", &temp);
            v[i][j] = '1' - temp;
        }
        getchar();
    }
    if(n == 1 && m == 1) printf("1");
    else printf("%d", bfs());
}

느낀점

  • 조용히 오석에서 하니 문제가 풀렸다. 다음 문제로 바로 달려보자 ㅎㅎ 화이팅!ㅎㅎ