[BOJ-1175]배달

S부터 이동을 해서 두개의 C 까지 도달하는 최소 이동횟수를 구하는 문제이다.

이동조건 : 이동은 이전 이동방향과 동일한 방향으로 이동이 불가능하다. 즉, RR LL UU DD 는 안된다.

[접근방법]

3차원 DP??

이를 구하기 위해서 이동방향[dir]과 위치[r][c]를 이용해서 BFS + DP 로 풀이하였다.

dp[dir][r][c] 는 이전에 dir방향으로 이동하여 [r][c]에 위치한 것을 의미한다.

이때 첫번째 C : C1 / 두번째 C : C2 라 표시했다.

dp 테이블에는 C1, C2 에 도달 할 수 있는 최소이동거리를 표시할 수 있다.

C1->C2 로 이동하는 c12 테이블을 만든다. 

C2->C1 로 이동하는 c21 테이블을 만든다. 

이 또한 [dir][r][c] 로 테이블을 만든다.

위 테이블에 결과 값을 도출 시킬 수 있다. 

값을 갱신하는 경우는 

현재 방향 hd ; // here_dir

현재 위치 [hr][hc] 로 한다.

이동하는 위치는 

이동할 위치로의 방향 i ;

이동 위치 [tr][tc] 로 한다.

이를 이용하여 

if(dp[i][tr][tc] > dp[hd][hr][hc] + 1) 인 경우 갱신을 시키며 구할 수 있고,

S->C1 / S->C2 를 구한 후 

c12, c21 테이블을 구한다.

그리고 c12 테이블에서는 C2의 위치에 저장된 값들 중 최소값이 최소 이동값이다.

c21 테이블에서는 C1의 위치에 저장된 값들 중 최소값이 최소 이동값이다.

이를 비교하여 최소 값을 구하면 된다.

*이 문제를 풀면서 BFS로 왔던 방향으로 돌아가지 않을 것이라 생각하면 반례가 팍팍 나온다. 

*즉, 왔던 방향으로도 이동 할 수 있으므로 고려하자.

*틀렸던 테케를 몇개 올려본다.

[test case+]

3 4 

S..C

...#

..C.

out : 9

4 4

S..C

...#

...C

out : 11

4 4

S..C

....

....

C...

out : 11

[C++11 Source Code DP]

#include<cstdio>
#include<queue>
using namespace std;
 
const int M = 55;
const int INF = 1 << 20;
int ROW, COL;
char imap[M][M];
 
const int dr[] = { -1, 0, +1, 0 }; // up left down right
const int dc[] = { 0 ,-1, 0, +1 };
 
int dp[4][M][M];
int c12[4][M][M];
int c21[4][M][M];
 
struct pos {
    int r, c;
    int dir;
    int mov;
    pos() {}
    pos(int ir, int ic, int id, int im) : r(ir), c(ic), dir(id), mov(im) {}
};
 
void init() {
    for (int r = 0; r < ROW; r++) {
        for (int c = 0; c < COL; c++) {
            for (int i = 0; i < 4; i++) {
                dp[i][r][c] = c12[i][r][c] = c21[i][r][c] = INF;
            }
        }
    }
}
 
int mn2(int a, int b) { return (a > b) ? b : a; }
 
int main() {
    scanf("%d%d", &ROW, &COL);
 
    pos start;
    pos finish[2];
    int index = 0;
    for (int r = 0; r < ROW; r++) {
        scanf("%s", imap[r]);
        for (int c = 0; c < COL; c++) {
            if (imap[r][c] == 'S') {
                start.r = r, start.c = c; // S
            }
            else if (imap[r][c] == 'C') {
                finish[index].r = r;
                finish[index].c = c;
                index++;
            }
        }
    }
 
    init();
    for (int i = 0; i < 4; i++) {
        dp[i][start.r][start.c] = 0;
    }
    
    
    queue<pos> Q;
    Q.push(pos(start.r, start.c, -1, -1));
    while (!Q.empty()) {
        pos here = Q.front(); Q.pop();
        int hr = here.r;
        int hc = here.c;
        int hd = here.dir;
        int hm = here.mov;
        if (hm > dp[hd][hr][hc]) continue;
 
        for (int i = 0; i < 4; i++) {
            int tr = hr + dr[i];
            int tc = hc + dc[i];
 
            if (i == hd) continue; // equal dir 
 
            if (tr < 0 || ROW <= tr || tc < 0 || COL <= tc) continue;
            if (imap[tr][tc] == '#') continue; // !
            if (dp[i][tr][tc] != INF) continue;
 
            if(hd == -1){
                dp[i][tr][tc] = 0 + 1;
                Q.push(pos(tr, tc, i, dp[i][tr][tc]));
            }
            else if (dp[i][tr][tc] > dp[hd][hr][hc] + 1) {
                dp[i][tr][tc] = dp[hd][hr][hc] + 1;
                Q.push(pos(tr, tc, i, dp[i][tr][tc]));
            }
        }
    } // S->C1 , S->C2
 
    Q = queue<pos>();
    int check = INF;
    for (int i = 0; i < 4; i++) {
        int& here = c12[i][finish[0].r][finish[0].c];
        int& there = dp[i][finish[0].r][finish[0].c];
        here = there;
        check = (check > here) ? here : check;
    }
    if (check == INF) {
        puts("-1");
        return 0;
    }
    for(int i = 0 ; i < 4 ; i++) Q.push(pos(finish[0].r, finish[0].c, i, -1));
    while (!Q.empty()) { // C1->C2
        pos here = Q.front(); Q.pop();
        int hr = here.r;
        int hc = here.c;
        int hd = here.dir;
        int hm = here.mov;
        if (hm > c12[hd][hr][hc]) continue;
 
        for (int i = 0; i < 4; i++) {
            int tr = hr + dr[i];
            int tc = hc + dc[i];
 
            if (i == hd) continue; // equal dir 
 
            if (tr < 0 || ROW <= tr || tc < 0 || COL <= tc) continue;
            if (imap[tr][tc] == '#') continue; // !
            //if (c12[i][tr][tc] != INF) continue;
            if (c12[i][tr][tc] <= c12[hd][hr][hc]) continue;
 
            if (c12[i][tr][tc] > c12[hd][hr][hc] + 1) {
                c12[i][tr][tc] = c12[hd][hr][hc] + 1;
                Q.push(pos(tr, tc, i, c12[i][tr][tc]));
            }
        }
    }
 
    Q = queue<pos>();
    check = INF;
    for (int i = 0; i < 4; i++) {
        int& here = c21[i][finish[1].r][finish[1].c];
        int& there = dp[i][finish[1].r][finish[1].c];
        here = there;
        check = (check > here) ? here : check;
    }
    if (check == INF) {
        puts("-1");
        return 0;
    }
    for (int i = 0; i < 4; i++) Q.push(pos(finish[1].r, finish[1].c, i, -1));
    while (!Q.empty()) { // C2->C1
        pos here = Q.front(); Q.pop();
        int hr = here.r;
        int hc = here.c;
        int hd = here.dir;
        int hm = here.mov;
        if (hm > c21[hd][hr][hc]) continue;
 
        for (int i = 0; i < 4; i++) {
            int tr = hr + dr[i];
            int tc = hc + dc[i];
 
            if (i == hd) continue; // equal dir 
 
            if (tr < 0 || ROW <= tr || tc < 0 || COL <= tc) continue;
            if (imap[tr][tc] == '#') continue; // !
            //if (c21[i][tr][tc] != INF) continue;
            if (c21[i][tr][tc] <= c21[hd][hr][hc]) continue;
 
            if (c21[i][tr][tc] > c21[hd][hr][hc] + 1) {
                c21[i][tr][tc] = c21[hd][hr][hc] + 1;
                Q.push(pos(tr, tc, i, c21[i][tr][tc]));
            }
        }
    }
    // operation end
 
    int ans0 = INF;
    int ans1 = INF;
    
    for (int i = 0; i < 4; i++) {
        int c1to2 = c12[i][finish[1].r][finish[1].c];
        int c2to1 = c21[i][finish[0].r][finish[0].c];
        ans0 = (ans0 > c1to2) ? c1to2 : ans0;
        ans1 = (ans1 > c2to1) ? c2to1 : ans1;
    }
 
    int ans = (ans0 > ans1) ? ans1 : ans0;
 
    if (ans == INF) puts("-1");
    else printf("%d\n", ans);    
 
    return 0;
}