문제
형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.
일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.
동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.
만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.
보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.
입력
줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.
예제 입력 1
3 7
3942178
1234567
9123532
예제 출력 1
5
예제 입력 2
1 10
2H3HH4HHH5
예제 출력 2
4
예제 입력 3
4 4
3994
9999
9999
2924
예제 출력 3
-1
예제 입력 4
4 6
123456
234567
345678
456789
예제 출력 4
4
예제 입력 5
1 1
9
예제 출력 5
1
예제 입력 6
3 7
2H9HH11
HHHHH11
9HHHH11
예제 출력 6
2
예제 입력 7
4 4
3HH2
H1HH
H2H1
2219
예제출력 7
8
예제 입력 8 (TIME OUT)
50 50
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H1
12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12
2H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H12H
예제 출력 8
66
풀이
void dfs(int y, int x, int cur)
{
dp[y][x] = cur;
int num = map[y][x] - '0';
for (int i = 0; i < 4; i++)
{
int m_y = y + (num * move_y[i]);
int m_x = x + (num * move_x[i]);
if (m_y < 0 || m_x < 0 || m_y >= N || m_x >= M)
continue;
if (map[m_y][m_x] == 'H')
continue;
if (visited[m_y][m_x])
{
dp[m_y][m_x] = INF;
return;
}
if (dp[m_y][m_x] < cur + 1)
{
visited[y][x] = true;
dfs(m_y, m_x, cur + 1);
visited[y][x] = false;
}
}
}dp[y][x]은 해당위치에서 최대 몇번의 동전을 던질 수 있는지를 나타낸다.
if (dp[m_y][m_x] < cur + 1)를 이용하여 서로다른 dfs탐색중 이미 방문 했었던 위치를 재 방문할때(사이클이 아닌경우), 이전에 방문하는데 이동한 거리보다 클 경우에만 dfs탐색을 계속하도록 하여 시간복잡도를 감소시켰다.
bool visited는 dfs탐색중 사이클이 발생하는지(사이클이 발생하면, 동전을 무한번 던질 수 있다)를 확인 하기위해 존재한다.
전체코드
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 987654321
char map[51][51];
bool visited[51][51];
int dp[51][51];
int move_y[4] = { 0, 1, 0, -1 };
int move_x[4] = { 1, 0, -1, 0 };
int N, M;
int sol = 0;
void input()
{
cin >> N >> M;
for (int y = 0; y < N; y++)
for (int x = 0; x < M; x++)
cin >> map[y][x];
}
void dfs(int y, int x, int cur)
{
dp[y][x] = cur;
int num = map[y][x] - '0';
for (int i = 0; i < 4; i++)
{
int m_y = y + (num * move_y[i]);
int m_x = x + (num * move_x[i]);
if (m_y < 0 || m_x < 0 || m_y >= N || m_x >= M)
continue;
if (map[m_y][m_x] == 'H')
continue;
if (visited[m_y][m_x])
{
dp[m_y][m_x] = INF;
return;
}
if (dp[m_y][m_x] < cur + 1)
{
visited[y][x] = true;
dfs(m_y, m_x, cur + 1);
visited[y][x] = false;
}
}
}
void solve()
{
visited[0][0] = true;
dfs(0, 0, 1);
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
sol = max(sol, dp[i][j]);
if (sol != INF)
cout << sol << "\n";
else
cout << "-1\n";
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
input();
solve();
}