https://www.acmicpc.net/problem/1103
1103번: 게임
줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는
www.acmicpc.net
1. 풀이방법
- 처음에는 단순 dfs로 접근하긴 했지만 (오랜만에 풀이라 일단 접근했음)
- 하면서도 분명 제대로 구현되도 시간초과가 뜨거나 스택오버플로우가 날 것 이라 생각했습니다.
- 처음시도는 역시나 시간초과
- 시간초과라면 dp테이블을 이용해보자는 생각 !
- 아, 근데 오랜만에 푸니까 dp적 머리가 잘 돌아가지 않아서 고생을 좀 했습니다....
- 우선 테이블을 모두 -1 처리를 하고 visit이 이미 true인 곳에 다시 오면 그건 싸이클이므로
- -1을 출력 (무한정 왔다리갔다리 가능)
- dp가 -1이 아닐경우 기존에 저장되어 있는 수와 현재의 루트에서 +1 (한번 더 이동) 해서 더 많은 이동횟수로 업데이트
- dfs +dp 라고 할 수 있겠네요. dfs는 간단한 수준이라 생략하겠습니다.
2. 주의사항
- 시간초과
3. 코드
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define endl "\n"
using namespace std;
int N, M;
int ground[50][50];
int dp[50][50];
bool visited[50][50];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
void Input(){
cin >> N >> M;
for (int i = 0; i < N; i++){
string inputs;
cin >> inputs;
for (int j = 0; j < inputs.length(); j++){
if (inputs[j] == 'H') ground[i][j] = 0;
else ground[i][j] = inputs[j] - '0';
}
}
}
int DFS(int x, int y){
if (x < 0 || y < 0 || x >= N || y >= M || ground[x][y] == 0) return 0;
if (visited[x][y] == true) // 무한반복이 가능
{
cout << -1 << endl;
exit(0);
}
if (dp[x][y] != -1) return dp[x][y]; // 바로 dp 테이블에서 리턴
visited[x][y] = true;
dp[x][y] = 0;
for (int i = 0; i < 4; i++){
int tx = x + (ground[x][y] * dx[i]);
int ty = y + (ground[x][y] * dy[i]);
dp[x][y] = max(dp[x][y], DFS(tx, ty) + 1);
}
visited[x][y] = false;
return dp[x][y];
}
int main(void){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
Input();
memset(dp, -1, sizeof(dp)); //dp 테이블 초기화
cout << DFS(0, 0) << endl;
return 0;
}
'알고리즘 문제풀이 > 다이나믹 프로그래밍' 카테고리의 다른 글
| 백준 1932 [C++] (0) | 2021.08.10 |
|---|---|
| 백준 3687 [C++] (0) | 2021.08.09 |
| 백준 1793 [C++] (0) | 2021.02.04 |
| 백준 1965 [C++] (0) | 2021.02.03 |
| 백준 1463 [C++] - 메모리초과 (0) | 2020.12.15 |