백준 1103 게임

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

1103번: 게임

 

1. 그래프를 이용해서 최장거리 + Cycle 체크로 푸는 사람도 있고 

2. DFS + 다이나믹 프로그래밍을 이용해서 풀수도 있다

 

2번이 더 간단하므로 2번으로 풀었다. 기회가 된다면 1번으로 풀어보는 것도 좋겠다. (되는지는 확실치 않음)

 

이 문제에서 주어지는 input은 그래프로 치자면 양방향 간선이라서 그냥 방문한 곳을 또 방문하면 무한 루프가 생겼다고 볼 수 있다. 그래서 재방문시 -1을 출력하고 프로그램을 종료한다.

 

그 외에는 일반적인 DFS + 메모이제이션(dp)이다.  

 

골드 1이고 정답률이 낮은 문제치고 어렵지않다.

/* 게임 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void input();
void solve();

int N, M, ANS;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };

char board[50][50];
int dp[50][50];
bool is_visit[50][50];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	input();
	solve();

	return 0;
}

void input() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
			board[i][j] = (board[i][j] == 'H' ? 'H' : board[i][j] - '0');
		}
	}
}

inline bool is_range(int r, int c) {
	return r >= 0 && r < N&& c >= 0 && c < M;
}

int dfs(int r, int c) {
	if (is_range(r, c) == false || board[r][c] == 'H') { // 끝났습니다.
		return 0;
	}
	int& ret = dp[r][c];
	if (ret != 0)
		return ret;

	if (is_visit[r][c]) {
		cout << -1 << '\n';
		exit(0);
	}

	int sum = 0;
	for (int i = 0; i < 4; i++) {
		int nr = r + dr[i] * board[r][c];
		int nc = c + dc[i] * board[r][c];
	
		is_visit[r][c] = true;
		sum = max(sum, dfs(nr, nc) + 1);
		is_visit[r][c] = false;
	}

	return ret = sum;
}

void solve() {
	cout << dfs(0, 0) << '\n';
}