[백준] 1103_게임 C++
in Study on Coding Test
DFS와 DP를 같이 사용해보는 문제
정답제출코드
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
int N, M, ans = 0;
vector<string> map;
bool visited[50][50];
int DP[50][50];
int m_max(int a, int b)
{
if (a > b)
return a;
else
return b;
}
int dfs(int x, int y)
{
if ((0 > x || x >= M || 0 > y || y >= N) || map[y][x] == 'H')
return 0;
if (visited[y][x])
{
cout << -1;
exit(0);
}
if (DP[y][x] != -1)
return DP[y][x];
int num = (map[y][x] - '0');
int dx[4] = {-num, num, 0, 0};
int dy[4] = {0, 0, -num, num};
visited[y][x] = true;
DP[y][x] = 0;
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
DP[y][x] = m_max(dfs(nx, ny) + 1, DP[y][x]);
}
visited[y][x] = false;
return DP[y][x];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for (int i = 0; i < N; ++i)
{
string _input;
cin >> _input;
map.push_back(_input);
}
memset(visited, false, sizeof(visited));
memset(DP, -1, sizeof(DP));
ans = dfs(0, 0);
cout << ans;
return 0;
}
최대의 관건은 dfs 탐색을 빠르게 하는 것이었다.
아니면 내가 모르는 사이에 무한루프에 빠진 것이었을 수도 있는데
이를 해결해야했다.
아무리 방법이 떠오르지 않아서 검색을 했는데 세상에 DP까지 써야하는 문제였다.
(x, y)가 주어진다면 그 자리에서 최대 몇번까지 이동할 수 있는 지를 구하는 방법인데
bottom-up 방식인지는 모르겠지만 난 아직 이런 식의 DP가 익숙하지가 않아서 큰일이다.
오답제출코드(시간초과)
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
int N, M, ans = 0;
vector<string> map;
bool visited[50][50];
bool Infinity = false;
int m_max(int a, int b)
{
if (a > b)
return a;
else
return b;
}
void dfs(int cnt, int x, int y)
{
if (Infinity)
return;
int num = (map[y][x] - '0');
int dx[4] = {-num, num, 0, 0};
int dy[4] = {0, 0, -num, num};
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if ((0 > nx || nx >= M || 0 > ny || ny >= N) || map[ny][nx] == 'H')
{
ans = m_max(cnt, ans);
continue;
}
if (visited[ny][nx])
{
Infinity = true;
return;
}
visited[ny][nx] = true;
dfs(cnt+1, nx, ny);
visited[ny][nx] = false;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for (int i = 0; i < N; ++i)
{
string _input;
cin >> _input;
map.push_back(_input);
}
memset(visited, false, sizeof(visited));
visited[0][0] = true;
dfs(1, 0, 0);
if (Infinity)
cout << -1;
else
cout << ans;
return 0;
}
DFS를 이용해서 정답코드를 구현하였다.
골드 5 문제에 있었던 한 칸씩만 이동하는 상황에서
이제는 때에 따라서 몇 칸을 이동하는지 개수가 다르다는 것이 첫 번째 문제였다.
간단하다. 그냥 전역변수에서 쓰던 dx 배열을 dfs함수 안으로 옮겨주고
dx에 들어가는 절댓값을 1대신 num으로 작성하였다.
int num = (map[y][x] - '0');
int dx[4] = {-num, num, 0, 0};
int dy[4] = {0, 0, -num, num};
그리고 두번째 문제는 무한으로 이동할 수 있는지 여부를 어떻게 판단하느냐이다.
음.. 이것도 의외로 간단하다.
같은 지점을 재방문 하게 된다면 무조건 무한으로 동전을 이동 시킬 수 있다.
따라서 방문을 했더니 해당 칸의 visited값이 true라면 Infinity 전역변수를 true로 반환,
Infinity가 true라면 ans 값에 상관없이 -1을 출력, 그렇지 않다면 ans를 출력하도록 구현하였다.
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if ((0 > nx || nx >= M || 0 > ny || ny >= N) || map[ny][nx] == 'H')
{
ans = m_max(cnt, ans);
continue;
}
if (visited[ny][nx])
{
Infinity = true;
continue;
}
visited[ny][nx] = true;
dfs(cnt+1, nx, ny);
visited[ny][nx] = false;
}
...
if (Infinity)
cout << -1;
else
cout << ans;
하지만 결과는 시간초과였다.
뭐가 문제였을까? dfs를 하는 과정에서 무한루프가 걸린 것인지,
시간이 오래걸리는 것인지 헤아릴 필요가 있었다.
결국엔 시간이 오래걸리는 것이었으며 이 부분은 DP로 해결하였다.
