BOJ : 1039 교환

---

[BOJ 1039(G3)리뷰]

굉장히 어려웠던 문제다.

처음엔 이걸 어떻게 BFS로 풀라는 건지 한참 고민을 했다.
계속 고민을 하다보니 그냥 모든 경우에 대하여 BFS를 돌리면 되는 간단한 문제인가? 라는 생각이 들어 바로 코딩을 했지만 계속 메모리초과&시간초과가 났다.

시간초과가 났던 이유는 너무나 당연했다. 두개의 값을 바꾸는 과정에서 중복되는 값이 큐에 푸쉬되는 현상이 반드시 일어 날 수있고, K가 클수록 시간복잡도 측면에서 매우 큰 손해를 보게 된다.

따라서 중복된 값을 큐에 넣지않도록 별도의 처리를 해줘야 한다. 다만 이때 각각의 연산마다 중복처리를 하는것을 독립적으로 계산해야 한다. 즉, 16375 에서 61375가 되고 다시 16375가 될 수 있는것이다. 각각의 연산횟수마다 독립적으로 처리하지 않는다면 이러한 경우를 뛰어넘게 된다.

따라서 가장 간단하면서 편리한 방법으로, 각각의 연산횟수마다 한번에 큐를 다 비워주는것이다. 
물론 BFS이기때문에 순차적으로 큐에 누적이 되지만, 방문배열을 초기화 하는과정을 명확하게 구분하기 위하여 새로운 연산이 시작될때마다 큐에 들어있는 모든값에 대하여 SWAP을 해주고, 방문배열을 초기화 해주면 된다.

그리고 연산횟수가 K번이 되었을때 최대값을 갱신해주면 문제에서 요구하는 조건을 만족할 수 있다.

/*
	21.01.11
	BOJ : 1103 게임 (https://www.acmicpc.net/problem/1103)
	DFS/DP
*/
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int N, M;
char board[51][51];
bool vis[51][51];
int dp[51][51];

int dfs(int r, int c) {
	if (board[r][c] == 'H' || r < 0 || c < 0 || r >= N || c >= M) { //벗어 났거나 구멍에 빠짐.
		return 0;
	}

	if (vis[r][c]) {
		cout << -1;
		exit(0);
	}

	if (dp[r][c] != -1) {
		//cout << "dp\n";
		return dp[r][c];
	}

	vis[r][c] = true;
	dp[r][c] = 0;
	int number = board[r][c]-'0';
	for (int dir = 0; dir < 4; dir++) {
		int nr, nc;
		if (dir == 0) {
			nr = r - number;
			nc = c;
		}
		else if (dir == 1) {
			nr = r;
			nc = c - number;
		}
		else if (dir == 2) {
			nr = r + number;
			nc = c;
		}
		else if (dir == 3) {
			nr = r;
			nc = c+number;
		}

		dp[r][c]=max(dp[r][c],dfs(nr, nc)+1);
	}
	vis[r][c] = 0;

	return dp[r][c];
}


int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> board[i];
	}

	for (int i = 0; i < N; i++) {
		fill(dp[i], dp[i] + M, -1);
	}

	cout<<dfs(0, 0);

	return 0;
}