[16933] 벽 부수고 이동하기 3

https://www.acmicpc.net/problem/16933

16933번: 벽 부수고 이동하기 3

<문제>

벽 부수고 이동하기 2번 문제의 코드에서, 낮과 밤을 나타내는 불리언 변수만 추가해서 queue에 넣어주었다.

 

처음에는 다음 dist를 curDist+2-flag처럼, 낮일경우 거리1 추가, 밤일경우 거리2를 추가하는 형태로 구현하려 했지만

그렇게 할경우 bfs의 특성인 '먼저 도착하는 해가 최적해'라는 특성이 적용되지 않아 queue 전체가 빌때까지 탐색을 진행해야만 한다.

결국 조기종료를 위해, 모든 가중치를 1로 설정하기 위해

밤에 벽을 부수는 경우는 제자리에 멈춰있는 경우를 push해서 해결했다.

 

<소스코드>

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
const int INF = 2121212121;
typedef struct { int y, x, cnt, dist; bool flag; } state;
queue <state>q;
int n, m, k, map[1001][1001];
bool visit[1001][1001][11];
int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
int f(void) {
    int i, y = 0, x = 0, answer = INF;
    q.push({ 0,0,0,1,true });
    visit[0][0][0] = true;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cur.y == n - 1 && cur.x == m - 1) {
            return cur.dist;
        }
        for (i = 0; i < 4; i++) {
            y = cur.y + dy[i];
            x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m)continue;
            if (map[y][x] == 1 && cur.cnt >= k)continue;
            if (map[y][x] == 0 && visit[y][x][cur.cnt] == false) {
                visit[y][x][cur.cnt] = true;
                q.push({ y,x,cur.cnt,cur.dist + 1 ,!cur.flag });
            }
            if (map[y][x] == 1 && cur.cnt < k && visit[y][x][cur.cnt + 1] == false) {
                if (cur.flag == true) {
                    q.push({ y,x,cur.cnt + 1,cur.dist + 1,false });
                    visit[y][x][cur.cnt + 1] = true;
                }
                else q.push({ cur.y,cur.x,cur.cnt,cur.dist + 1,true });
            }
        }
    }
    return -1;
}
int main(void) {
    scanf("%d %d %d", &n, &m, &k);
    if (n == 1 && m == 1) {
        printf("1");
        return 0;
    }
    int i, j;
    char s[1010] = { 0 };
    for (i = 0; i < n; i++) {
        scanf("%s", s);
        for (j = 0; s[j]; j++) {
            if (s[j] == '0')map[i][j] = 0;
            else if (s[j] == '1')map[i][j] = 1;
        }
    }
    printf("%d", f());
    return 0;
}

bool의 토글은 if문을 사용하면 직관적으로 처리가 가능하지만 !flag처럼 작성하면 코드의 길이가 줄어든다.

'!'가 너무 잘 안보인다면, !!!flag나 !!!!!flag처럼 홀수개로 맞춰서 여러개 작성하는 방법도 있기는 하겠다.