백준 16137 견우와 직녀

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

16137번: 견우와 직녀

#include<stdio.h>
#include<queue>
#include<string.h>
#define NSIZE 10
#define MSIZE 20
using namespace std;
int N, M;
int input[NSIZE][NSIZE];
int chk[NSIZE][NSIZE];
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
int ret = 0;
int Min = 0x7fffffff;
struct Data {
    int y, x, cnt, time;
};
void init() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &input[i][j]);
        }
    }
}
bool chkHole(int y,int x) {
    int cnt = 0;
    for (int dir = 0; dir < 4; dir++) {
        int ny = y+dy[dir]; int nx = x+dx[dir];
        int nny = y+dy[(dir+1)%4]; int nnx = x+dx[(dir + 1) % 4];
 
        if (0 <= ny && ny < N && 0 <= nx && nx < N&& 0 <= nny && nny < N && 0 <= nnx && nnx < N) {
            if (input[ny][nx] == 0 && input[nny][nnx] == 0) return false;
        }
    }
    return true;
}
void bfs() {
    queue<Data>q;
    memset(chk, 0x32, sizeof(chk));
    q.push({ 0,0,0,0 });
    chk[0][0] = 1;
    while (!q.empty()) {
        Data c = q.front(); q.pop();
        if (c.y == N - 1 && c.x == N - 1) {
            ret = chk[c.y][c.x];
            return;
        }
        for (int dir = 0; dir < 4; dir++) {
            Data n;
            n.y = c.y + dy[dir];
            n.x = c.x + dx[dir];
            n.cnt = c.cnt+1;
            n.time = c.time;
            if (0 <= n.y && n.y < N && 0 <= n.x && n.x < N) {
                if (chk[n.y][n.x]>=n.cnt && input[n.y][n.x] >= 1) {
                    if (input[n.y][n.x] >= 2&&n.time==0) {
                        if ( n.cnt%input[n.y][n.x] == 0) {
                            chk[n.y][n.x] = n.cnt;
                            n.time = 1;
                            q.push(n);
                        }
                        else {
                            n.cnt = n.cnt + (input[n.y][n.x]-(n.cnt % input[n.y][n.x]));
                            chk[n.y][n.x] = n.cnt;
                            n.time = 1;
                            q.push(n);
                        }
                    }
                    else if(input[n.y][n.x]==1) {
                        if (n.time == 1)n.time = 0;
                        chk[n.y][n.x] = n.cnt;
                        q.push(n);
 
                    }
                }
            }
        }
    }
}
void meeting() {
    ret = 0x7fffffff;
    bfs();
    if (Min > ret)Min = ret;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (input[i][j] == 0 && chkHole(i, j)) {
                input[i][j] = M;
                ret = 0x7fffffff;
                bfs();
                if (Min > ret)Min = ret;
                input[i][j] = 0;
            }
        }
    }
}
int main(void) {
    init();
    meeting();
    printf("%d\n", Min);
    return 0;
}

이걸 보면 n.time 이라는 변수에 1로 오작교 건넜음을 체크해주면됩니다. 

하지만 다시 오작교가 아닌 거리에 오면 0으로 만들어줘야함을 잊지마세요.

 

이제 마지막으로 3번은 

소스를 보시면 

이건데 왜 저렇게 되냐 말씀드리면 이렇습니다. 

이해가 안되실 수 있는데 이해가 되셨으면 좋겠습니다. 저렇게 하면 답이 통과가 되더라구요

오늘도 여기까지이고 즐거운 코딩하세요.