백준 16137 견우와 직녀

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

16137번: 견우와 직녀

예전에 통과한 문제 였는데 데이터 추가로 인해서 틀렸다로 바꼈습니다. 그래서 다시 통과 상태로 만들기 위해 

문제를 풀었습니다. BFS 탐색으로 문제를 푸는것인데 예전방식도 맞다고 생각 했지만 역시나

알고리즘을 풀때는 애매하면 언젠가 이렇게 틀린문제로 돌아온다는것을 경험하게되었습니다.

 

대략적으로 소스의 방식은 예전에 비해 많이 바뀌었지만 가장 큰 실수를 했던것은 아무래도 오작교를 한개더 

놓을 수 있는 위치를 잘못 한것이 아닐까합니다.

저번에는 전체적인 비엡도 문제가 있었지만 이번에 놓는위치를 확인해주는 소스도 실수가 있었다는것을 알게

되었습니다.

 

저렇게 동그라미가 그려져 있는 부분에는 오작교를 놓을 수없습니다. 이를 걸러주기위해서

인풋으로 들어온곳에 0 인 인덱스의 y,x를 중심으로

4번 검사하면되는데 아래 소스가 위의 그림을 나타냅니다.

이부분을 왜 이렇게 했는지 의문을 가지시는 분이 계실것 같아서

0 일때 +1 이면 1

1일때 2

2일때 3

3일때 0 이되어야하는데 +1를 하면 4가 됩니다. 이때 그것을 0으로 만들어준다고 생각하면

이해하기 편하실것입니다. 

이렇게해서 양쪽이 0이면 놓을 수없는 위치로 false를 반환하고 

그런곳이 없으면 true 참을 반환하여 큐를 돌게 됩니다.

전체적인 큐는 오작교는 두번 연속 건널수 없기때문에

그냥 길인경우와 오작교인 경우를 나누어

오작교인 조건에서는 다음이 오작교라면 이전에 있는위치가 그냥 길인 경우에만 큐에 넣을수 있도록 구현을

하였습니다.

그리고 오작교를 넘어갈때 주기가 맞으면 +1이되서 넘어가지만 그렇지 않은경우 그 남은 주기를 +1과 그 위치의 오작교 주기를 더한것을 빼서 계산을 하며 오작교가 주기가 되었을때 시간을 넣어 최소의 거리로 현재 넘어갈 위치가

이전 보다 더 빨리 도달했으면 최신화를 해주면서 N-1 , N-1에 도달했을때 이동거리의 최소값을 뽑아내는 식으로

문제를 풀었습니다 아래 소스를 참고하시면 될것입니다.

 

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int N, M;
int input[11][11];
int dy[] = { 0,1,0,-1 };
int dx[] = { -1,0,1,0 };
/*
00 01 02
10 11 12
20 21 22
 
*/
int Min = 0x7fffffff;
int visit[11][11];
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 chk(int y, int x) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        int ny1 = y + dy[(i + 1) % 4];
        int nx1 = x + dx[(i + 1) % 4];
        if (0 <= ny && 0 <= ny1 && ny < N&&ny1 < N && 0 <= nx && 0 <= nx1 && nx < N&&nx1 < N) {
            if (input[ny][nx] == 0 && input[ny1][nx1] == 0) return false;
        }
    }
    
    return true;
}
typedef struct Data {
    int y, x, cnt;
}Data;
void bfs() {
    queue<Data>q;
    q.push({ 0, 0, 0 });
    while (!q.empty()) {
        Data c = q.front(); q.pop();
        if (c.y == N - 1 && c.x == N - 1) {
            if (Min > c.cnt) Min = c.cnt;
        }
        for (int d = 0; d < 4; d++) {
            Data n; n.y = c.y + dy[d]; n.x = c.x + dx[d], n.cnt = c.cnt + 1;
            if (0 <= n.y&&n.y < N && 0 <= n.x&&n.x < N) {
                if (visit[n.y][n.x] > n.cnt&&input[n.y][n.x] == 1) {//그냥 길 이동
                    visit[n.y][n.x] = n.cnt;
                    q.push(n);
                }
                else if (input[n.y][n.x] >= 2) {//오작교인 경우
                    int time = n.cnt%input[n.y][n.x];// 주기가 맞는지 확인
                    if (input[c.y][c.x] == 1 && time == 0 && visit[n.y][n.x] > n.cnt) {// 주기가 맞으면
                        visit[n.y][n.x] = n.cnt;
                        q.push(n);
                    }
                    else if (input[c.y][c.x] == 1 && time != 0) {//주기가 맞지 않으면 계산해서 올라가게 하기
                        n.cnt = n.cnt + input[n.y][n.x] - (n.cnt%input[n.y][n.x]);
                        if (visit[n.y][n.x] > n.cnt) {
                            visit[n.y][n.x] = n.cnt;
 
                            q.push(n);
                        }
                    }
                }
            }
        }
 
    }
 
}
 
int main(void) {
    init();
    memset(visit, 0x32, sizeof(visit));
    visit[0][0] = 0;
    bfs();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (input[i][j] == 0 && chk(i, j)) {
                input[i][j] = M;
                memset(visit, 0x32, sizeof(visit));
                visit[0][0] = 0;
                bfs();
                input[i][j] = 0;
            }
        }
    }
    printf("%d\n", Min);
    return 0;
}