[BOJ-13903]출근

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

* 조건을 제대로 읽지 않아서 1번 틀렸었다.

[문제요약]

1. 세로 블록만 밟음.

2. 시작은 첫번째 행( ROW (0) ) 세로 블록 중 어느 곳이던 가능.

3. 특정 규칙대로 이동함. (현재위치 + 특정규칙)

4. 첫번째 행(0)에서 마지막 행(ROW-1) 도착하면 출근에 성공함.

5. 4.의 과정을 수행하는데, 최소한의 이동으로 하고 싶음.

[입력]

ROW COL ~ [블록의 크기]

[출근할 블록의 정보]

MOV ~ [규칙 개수]

규칙1 ~ [+mov_row , +mov_col

규칙2 ..

...

규칙MOV ..

순서대로 

블록의 크기

블록의 정보 세로의 경우 1, 가로의 경우 0

규칙 개수

규칙들이 주어짐. 규칙은 현재위치 (here_row, here_col) 에서 (+ 규칙row, +규칙col) 을 더한 값으로 구함.

[출력]

최소 이동 횟수를 출력함. 만약 도달하지 못했을 경우 -1

[접근방법]

BFS를 이용한다. 

여기서 고려해야할 것이 처음 시작할 BFS 위치는 한 개가 아닌 여러개가 될 수 있음. [문제요약-2] 를 고려함.

그래서 모든 시작점을 큐에 넣는다.

이동 위치를 선정할 때 

1) 세로블록(1) 이동해야함. [문제요약-1] 

2) 보도블록 크기안에서만 이동해야함.

3) 어느 위치에서던 이동할 때 처음 도달하는 경우 최소거리임. 

큐에서 꺼내어 이동할 수 있는 위치를 찍었을 때 trace 를 갱신하기 때문에 

이후 큐에서 나온 위치에서 동일한 위치로 이동할 수 있다고 하더라도 먼저 나온 이동거리보다 짧아질수는 없음.

이를 이용해서 큐가 비어있을 경우까지 반복하여 BFS를 수행.

BFS 를 수행을 마친 후 마지막 위치에 도달한 값 중 최소값을 출력 함. 하지만 도달한 적이 없는 경우에 -1을 출력.

이제 위 접근방법을 이용하여 코드를 작성함.

imap[M][M] : 출근할 블록의 정보를 저장함.

trace[M][M] : trace[r][c] 는 해당 블록[r][c] 에 도달 할 최소 이동횟수를 저장함. 

처음에 모두 -1로 초기화 시키며,

bfs를 돌리기 전에 

for c ~ 0 to COL-1 : imap[0][c] 이 세로(1) 로 된 곳이면 위치를 큐에 넣으며 

trace[0][c]를 0으로 갱신.

vi dr, dc 는 이동 규칙을 저장함. MOV 라는 변수가 있으므로 dr 와 dc 벡터의 크기는 MOV

이를 이용하여 위치를 바꿔줌.

이 방법으로 문제를 풀이함.

#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<cstring>
#define prow first
#define pcol second
#define din1(a) scanf("%d", &a)
#define din2(a,b) scanf("%d%d", &a, &b)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int M = 1111;
const int INF = 987654321;
vi dr;
vi dc;
int imap[M][M];
int trace[M][M];
int ROW, COL;
int MOV;
 
bool is_move(int r, int c) {
    if (!(0 <= r && r < ROW && 0 <= c && c < COL)) return false;
    if (imap[r][c] != 1) return false; // add-code : 조건 제대로 읽지못함.
    if (trace[r][c] != -1) return false;
    return true;
}
 
int bfs() {
    queue<pii> Q;
    for (int i = 0; i < COL; i++) {
        if (imap[0][i]) {
            Q.push(mp(0, i));
            trace[0][i] = 0;
        }
    } // init mov
 
    while (!Q.empty()) {
        int hr = Q.front().prow;
        int hc = Q.front().pcol;
        Q.pop();        
 
        for (int i = 0; i < MOV; i++) {
            int tr = hr + dr[i];
            int tc = hc + dc[i];
 
            if (is_move(tr, tc)) {
                trace[tr][tc] = trace[hr][hc] + 1;
                Q.push(mp(tr, tc));
            }
        }
    } // bfs
 
    int ans = INF;
    for (int i = 0; i < COL; i++) {
        int here = trace[ROW - 1][i];
        if (here > -1) ans = (ans < here) ? ans : here;
    } // search ans
    if (ans == INF) ans = -1;
 
    return ans;
}
 
void init() {
    memset(trace, -1, sizeof(trace));
}
 
int main() {
    init();
    din2(ROW, COL);
    for (int r = 0; r < ROW; r++) {
        for (int c = 0; c < COL; c++) {
            din1(imap[r][c]);
        }
    } // input map
    
    din1(MOV);
    for (int i = 0; i < MOV; i++) {
        int mr, mc;
        din2(mr, mc);
        dr.pb(mr), dc.pb(mc);
    }
    
    printf("%d", bfs());    
    return 0;
}