[Jungol] 정올 2058 고돌이 고소미

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2275&sca=4040

 Input 

5

2 2 4 4

3 4 4 2

1 0 1 1 1

0 0 0 0 0

1 1 0 0 1

1 0 0 0 1

1 0 0 1 1

 

 Output 

3 

보통의 BFS 문제는 지날 수 없는 곳을 제외해서 최단경로를 탐색합니다.

하지만 위와 같이 somi 집에 도착하여 움직이지 않게 되면 dori는 somi의 근처로는 지나갈 수 없으므로

dori의 집으로 돌아가는 길이 없습니다. 따라서, 위의 case 처럼 시작위치에서 실질적인 최단거리가 되지 않더라도

두 고슴도치가 모두 집에 도착하기 위해서는 어느 한쪽이 길을 비켜주는 경로가 필요하며

그 중에서 최소 이동거리를 찾아야 합니다.

(시뮬레이션 과정에서도 확인가능하지만 고슴도치가 움직이지 않는 경우도 존재)

시뮬레이션

0. 

 

1. 한 쪽이 움직이지 않는 선택도 가능합니다.

    

2. 

 

3. 이제서야 동시에 움직입니다.

    

4. 

 

5. 

 

6. 

 

7. 

 

8. 

 

9. 

 

10. 

 

11. 

 

12. 소미는 집에 도착하였습니다.

 

13. 돌이까지 집에 도착하였습니다.

 

문제 이해를 위한 Q&A

- 인접하지만 않는다면 고돌이(고소미)가 갔던 곳을 고소미(고돌이)가 갈 수 있는가? Yes

- 고슴도치가 어떤 상태일 때 취할 수 있는 경우의 수? 9가지 ← 상하좌우(4) + 대각선(4) + 움직이지 않는 것(1)

- 고돌이와 고소미는 동시에 움직이기 때문에 두 고슴도치가 가질 수 있는 경우의 수? 9 × 9 = 81

    → 4차원 배열 state[][][][]사용

    ex) state[1][2][4][5] = 고돌이 (1, 2)와 고소미 (4, 5) 방문한 적 있음

  

처리 내용

- 고슴도치가 서로 인접하여 이동할 수 없는 경우 : 행 간격과 열 간격이 모두 1이하인 경우

- 고돌이와 고소미 마을 최대 크기 25 × 25

    → 고돌이와 고소미가 가질 수 있는 상태? 최대 25  × 25  × 25  × 25

    → 제출코드에서는 배열을 벗어나는 경계선을 쉽게 처리하기 위해 state[27][27][27][27]로 처리 → 큐의 크기도 274 )

        또한, 경계선을 『0』 으로 처리하였기에 지나갈 수 없는 웅덩이를 동일하게 처리하기 위해

        입력받은 데이터 반대로 처리 (1 ↔ 0)

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = 25 + 2; 
const int INF = LM * LM * LM * LM;
inline int abs(int a) { return a < 0 ? -a : a; }
inline int isMeet(int doriX, int doriY, int somiX, int somiY) {
    return (abs(doriX - somiX) <= 1 && abs(doriY - somiY) <= 1);
}
int dr[] = { -1, 1, 0, 0, -1, -1, 1, 1, 0 };
int dc[] = { 0, 0, -1, 1, -1, 1, -1, 1, 0 };
int N, doriStartX, doriStartY, doriEndX, doriEndY;
int somiStartX, somiStartY, somiEndX, somiEndY;
int A[LM][LM], state[LM][LM][LM][LM];
int fr, re;
struct Queue {
    int doriX, doriY, somiX, somiY, lev;
} que[INF];
 
 
void input() {
    scanf("%d", &N);
    // dori 시작과 끝 위치
    scanf("%d%d%d%d", &doriStartX, &doriStartY, &doriEndX, &doriEndY);
    // somi 시작과 끝 위치
    scanf("%d%d%d%d", &somiStartX, &somiStartY, &somiEndX, &somiEndY);
 
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            scanf("%d", A[i] + j);
            A[i][j] = !A[i][j]; // 0과 1을 반대로 저장
        }
    }
}
 
void push(int doriX, int doriY, int somiX, int somiY, int lev) {
    // 이미 방문하였거나 돌이와 소미가 이동하려는 곳이 웅덩이인 경우
    if (state[doriX][doriY][somiX][somiY] || !A[doriX][doriY] || !A[somiX][somiY]) return;
    // 두 고슴도치가 인접하는 경우
    if (isMeet(doriX, doriY, somiX, somiY)) return;
    // 방문 표시
    state[doriX][doriY][somiX][somiY] = 1;
    que[re++] = { doriX, doriY, somiX, somiY, lev };
}
 
int BFS() {
    Queue cur;
    push(doriStartX, doriStartY, somiStartX, somiStartY, 0);
    while (fr < re) {
        cur = que[fr++];
        // 두 고슴도치가 모두 집에 도착한 경우
        if (cur.doriX == doriEndX && cur.doriY == doriEndY &&
            cur.somiX == somiEndX && cur.somiY == somiEndY) {
            return cur.lev;
        }
 
        // 두 고슴도치가 가질 수 있는 모든 경우
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                push(cur.doriX + dr[i], cur.doriY + dc[i],
                    cur.somiX + dr[j], cur.somiY + dc[j],
                    cur.lev + 1);
            }
        }
    }
    return -1;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    printf("%d", BFS());
}