[C++] 백준(BOJ) - 1513 : 경로 찾기
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
세준이는 크기가 N*M인 직사각형 도시에 살고 있다. 또, 세준이의 집은 (1, 1)에 있고, 학원은 (N, M)에 있고, 오락실이 C개 있다.
세준이의 현재 위치가 (r, c) 일 때, (r+1, c) 또는 (r, c+1)로만 이동할 수 있다. 오락실을 방문할 때는 규칙이 하나 있는데, 오락실 번호가 증가하는 순서대로 가야한다는 것이다. 2번 오락실을 먼저 가고, 그 후에 1번 오락실을 가면 안 되고, 2번 오락실을 가려면, 그 전에 아무 오락실도 가지 않거나, 1번 오락실을 방문했을 때만 가능하다.
세준이는 오락실을 K번 방문해서 학원에서 도착하는 경로의 경우의 수가 궁금해지기 시작했다. 오락실을 0개 방문했을 때부터, C개 방문했을 때 까지 경우의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N M C가 주어진다. N과 M은 50보다 작거나 같은 자연수이고, C는 50보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 C개의 줄에 1번 오락실부터 C번 오락실까지 위치가 차례대로 주어진다. 오락실의 위치가 중복되는 경우는 없지만, 오락실의 위치가 (1,1) 또는 (N,M)일 수도 있다.
출력
첫째 줄에 0개 방문했을 때, 1개 방문했을 때, …, C개 방문했을 때 총 경로의 개수를 한 줄에 공백을 사이에 두고 출력한다. 경로의 개수는 1,000,007로 나눈 나머지를 출력한다.
알고리즘
- DP
- DFS
풀이
- 순차적으로 방문한다 => idx 값을 맵에 저장하여 사용할 수 있다
- 그 전에 방문한 오락실 번호를 알고 있어야 한다 (prev 상태값 dp에 추가)
- 방문하는 오락실 수(cnt 상태값)에 따라 경우의 수 구하고 합하기
- 경로 탐색과 두 방향 DFS가 결합된 문제
- 두방향 DFS는 재귀함수의 두번 호출로도 처리할 수 있다
- 두 방향 탐색이므로 (y,x)는 커지는 방향으로만 진행됨
- 기저 조건을 유연하게
y > n || x > m 인 경우와y == n && x == m 인 경우로 나눠서 종료 조건 만들 수 있다
- 기저 조건을 유연하게
- 모듈러 연산을 각 res를 구할 때마다 해주어서 숫자를 작게 만들 수 있다
코드
// BOJ - 1513 : 경로 찾기
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000007;
int n, m, c, y, x, a[51][51], dp[51][51][51][51];
int go(int y, int x, int cnt, int prev)
{
if (y > n || x > m) return 0;
if (y == n && x == m)
{
if (cnt == 0 && a[y][x] == 0) return 1;
if (cnt == 1 && a[y][x] > prev) return 1; // 도착지점이 오락실이고 prev보다 a[y][x]가 클 때 (가능)
return 0;
}
int& res = dp[y][x][cnt][prev];
if (res != -1) return res;
res = 0;
if (a[y][x] == 0)
{
res = (go(y + 1, x, cnt, prev) + go(y, x + 1, cnt, prev)) % mod;
}
else if (a[y][x] > prev && cnt >= 1)
{
res = (go(y + 1, x, cnt - 1, a[y][x]) + go(y, x + 1, cnt - 1, a[y][x])) % mod;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(dp, -1, sizeof(dp));
cin >> n >> m >> c;
for (int i = 1; i <= c; i++)
{
cin >> y >> x;
a[y][x] = i;
}
for (int i = 0; i <= c; i++)
{
cout << go(1, 1, i, 0) << ' ';
}
return 0;
}
평가
- DP와 DFS 문제는 코딩테스트 단골 문제이므로 문제 해법을 잘 익힌다
- DP
- 기저사례
- 메모이제이션
- 로직
- 초기화
- DFS
- 종료조건
- 탐색
- 재귀
- DP
