[BFS/DFS] C11 백준 2206 벽 부수고 이동하기 풀이

문제

• 2206

풀이 과정

• bfs 문제인데 여기서 문제는 최단거리 값에서 벽을 1번 이동할 수 있다는 조건을 포함해야 된다는 것...!
  • 처절하게 3번 틀렸는데..

if (nx >= 0 && nx < n && ny >= 0 && ny < m && visit[nx][ny] == 0) {
  if (map[nx][ny] == '0') {
    visit[nx][ny] = visit[cur.x][cur.y] + 1;
    enqueue(nx, ny, cur.flag);
  } else if (map[nx][ny] == '1' && cur.flag == 0) {
    visit[nx][ny] = visit[cur.x][cur.y] + 1;
    enqueue(nx, ny, cur.flag + 1);
  }
}

• 처음에 그냥 큐에서 플래그로 부순거 안부순거 확인하고 값 넣으면 되겠지 싶어서 위의 코드처럼 조건줬다가 개같이 틀렸다
• 생각해보니 이렇게 되면 부수는 경로, 안 부수는 경로가 서로 구분이 안되서 값을 덮어 씌워 버린다
  • 고로 큐 뿐만아니라, 최단 거리를 적는 visit 배열도 확장 시켜줘야 한다
  • 부술 때 [][][1], 안 부술 때 [][][0] 로 나눠서 저장해야 함

#include <stdio.h>

#define MAX 1001

typedef struct Que {
    int x;
    int y;
    int flag;
} Q;

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

int n,m;
char map[MAX][MAX];
int visit[MAX][MAX][2];

Q que[MAX*MAX*2];
int front;
int rear;

void enqueue(int x, int y, int flag) {
    que[rear].x = x;
    que[rear].y = y;
    que[rear].flag = flag;
    rear++;
}

Q dequeue() {
    return que[front++];
}

int bfs(int x, int y, int flag) {
    visit[x][y][flag] = 1;
    enqueue(x, y, flag);
    
    while (front < rear) {
        Q cur = dequeue();
        
        if (cur.x == n-1 && cur.y == m-1) return visit[cur.x][cur.y][cur.flag];
        
        for (int i=0; i<4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (map[nx][ny] == '0' && visit[nx][ny][cur.flag] == 0) {
                    visit[nx][ny][cur.flag] = visit[cur.x][cur.y][cur.flag] + 1;
                    enqueue(nx, ny, cur.flag);
                } else if (map[nx][ny] == '1' && cur.flag == 0 && visit[nx][ny][1] == 0) {
                    visit[nx][ny][1] = visit[cur.x][cur.y][cur.flag] + 1;
                    enqueue(nx, ny, 1);
                }
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d %d", &n, &m);
    
    for (int i=0; i<n; i++) {
        scanf("%s", map[i]);
    }
    
    int result = bfs(0, 0, 0);
    if (result == -1) {
        printf("-1");
    } else {
        printf("%d", result);
    }
    return 0;
}