[BOJ] 10164 격자상의 경로

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

10164번: 격자상의 경로

---

문제

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.) 

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 

• 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
• 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다. 

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

• 1 → 2 → 3 → 8 → 9 → 10 → 15
• 1 → 2 → 3 → 8 → 13 → 14 → 15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라. 

---

입력

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.

---

출력

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다. 

---

풀이

dp문제인데 탐색을 어떻게 해야하는지 헷갈려서 푸는데 오래 걸렸다.

내가 여태까지 풀었던 dp는 recursive하거나 iterative하게 탐색하였는데 이번 문제는 bfs를 이용해서 탐색해야했다.

 

N=3, M=5, K=8 일 때 탐색 경로는 위와 같다. bfs를 돌 때 오른쪽 방향과 아래 방향만 확인하면 된다는 것을 알 수 있다.

조심해야 할 점은 bfs를 돌 때, 이미 방문처리한 곳은 push를 못하지만 dp값은 넘겨줘야 한다는 것이다.

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <set>

#define p(a, b) make_pair(a, b)
#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

ll dp[15][15];
bool visit[15][15];
int N,M,K;
int k_y,k_x;
int dy[]={0,1}; //아래
int dx[]={1,0}; //오른쪽

void bfs(int start_y,int start_x,int end_y,int end_x){
    queue<pair<int,int> > q;
    q.push(p(start_y,start_x));
    visit[start_y][start_x]=true;
    
    while(!q.empty()){
        int y=q.front().first, x=q.front().second; q.pop();
        if(y==end_y&&x==end_x) break;
        for(int i=0;i<2;i++){
            int ny=y+dy[i], nx=x+dx[i];

            if(ny<=end_y&&nx<=end_x){
                dp[ny][nx]+=dp[y][x]; //갈 수 있는 곳이라면 무조건 dp값을 넘겨준다.
                if(!visit[ny][nx]){
                    visit[ny][nx]=true;
                    q.push(p(ny,nx));
                }
            }
        }
    }
}

void input() {
    cin>>N>>M>>K;
    int idx=1;
    if(K==0) K=N*M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(idx++==K){k_y=i,k_x=j;break;}
        }
    }

}

void init() {
}


void solution() {
    dp[0][0]=1;
    bfs(0,0,k_y,k_x);
    if(K!=N*M){ //K가 0인 경우 K부터 목적지까지 구해줘야한다.
        bfs(k_y,k_x,N-1,M-1);
    }
    cout<<dp[N-1][M-1];
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}