백준 1103번 게임 , 1256번 사전

음 dfs를 아직도 잘 이해하지 못한거같다. 

 

두가지가 중요 포인트였다.

 

1. 해당 노드에서 이동 횟수를 어떻게 저장할 것이냐 

 

2. 무한 루프를 도는지 어떻게 알것인가.

 

1번은 그럭저럭 생각했는데. 2번이 문제였다. 근데 방향을 포함해서 dp를 하려했던 내 생각이 틀린것이 그렇게 할 필요가 없는게 

 

해당 지점에서 이동한다 생각하고, dfs가 가장 깊이 갔다가 그 다음 지점들(4방향을 차례로 방문한다) 생각하면 방향을 포함 시킬 필요가 없었다.

 

아래 블로그를 참고 했다... 혼자 도저히 오래걸려서

https://lcs11244.tistory.com/63

[백준] 1103 - 게임

 

 

난 내 두코드의 차이를 모르겠다....

 

해당 예제에 대해서는 안되는데 왜 안되지??

 

5 5
4HHH9
HHHHH
HHH12
HHHHH
3HH2H

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<algorithm>
#include<string.h>
using namespace std;

#define MAXV 1000000000

int dir_r[4] = { 0,0,1,-1 };
int dir_c[4] = { 1,-1,0,0 };
int dp[51][51] = { 0 };
bool vis[51][51] = { false };

int arr[51][51];
int R, C;
int maxv = 0;

struct coord {
	int r, c;
	int dir, dis;
};

bool full = false;

int dfs(int r, int c) {
	int nr, nc;

	if (arr[r][c] == -1) {
		return 0;
	}
	if (r < 0 || r >= R || c < 0 || c >= C) {
		return 0;
	}
	if (vis[r][c]==1) {
		cout << -1 << "\n";
		exit(0);
	}

	if (dp[r][c] > 0)
		return dp[r][c];

	vis[r][c] = 1;
	for (int i = 0; i < 4; i++) {
		nr = dir_r[i] * arr[r][c] + r;
		nc = dir_c[i] * arr[r][c] + c;
		
		int w = dfs(nr, nc)+1;
		
		dp[r][c] = dp[r][c] > w ? dp[r][c] : w;
	}
	vis[r][c] = 0;

	return dp[r][c];
}

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

	//freopen("input.txt", "r", stdin);
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++)
		{
			char tmp;
			cin >> tmp;
			if (tmp == 'H')
				arr[i][j] = -1;
			else
				arr[i][j] = tmp - '0';
		}
	}

	memset(vis, 0, sizeof(vis));
	dfs(0, 0);

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			for (int k = 0; k < 4; k++) {
				if (dp[i][j] > maxv)
					maxv = dp[i][j];
			}
		}
	}
	
	cout << maxv;

	return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<algorithm>
#include<string.h>
using namespace std;

#define MAXV 1000000000

int dir_r[4] = { 0,0,1,-1 };
int dir_c[4] = { 1,-1,0,0 };
int dp[51][51] = { 0 };
bool vis[51][51] = { false };

int arr[51][51];
int R, C;
int maxv = 0;

struct coord {
	int r, c;
	int dir, dis;
};

bool full = false;

int dfs(int r, int c, int depth) {
	int nr, nc;

	if (arr[r][c] == -1) {
		return depth;
	}
	if (r < 0 || r >= R || c < 0 || c >= C) {
		return depth;
	}
	if (vis[r][c]==1) {
		cout << -1 << "\n";
		exit(0);
	}

	if (dp[r][c] > 0)
		return dp[r][c];

	vis[r][c] = 1;
	for (int i = 0; i < 4; i++) {
		nr = dir_r[i] * arr[r][c] + r;
		nc = dir_c[i] * arr[r][c] + c;
		
	//	vis[nr][nc] = 1;
		int w = dfs(nr, nc, depth+1);
	//	vis[nr][nc] = 0;

		dp[r][c] = dp[r][c] > w+1 ? dp[r][c] : w+1;
	}
	vis[r][c] = 0;

	return dp[r][c];
}

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

	freopen("input.txt", "r", stdin);
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++)
		{
			char tmp;
			cin >> tmp;
			if (tmp == 'H')
				arr[i][j] = -1;
			else
				arr[i][j] = tmp - '0';
		}
	}

	memset(vis, 0, sizeof(vis));
	dfs(0, 0, 0);


	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {

				if (dp[i][j] > maxv)
					maxv = dp[i][j];

		}
	}
	
	cout << maxv;

	return 0;
}

(아래 코드) 나처럼 깊이를 해당 노드에 저장한다면 dp[r][c]의 의미가 조금 달라지는거 같다.

내 dp[r][c]는 r,c를 지나서 갈 수 있는 가장 깊었을때를 반환하게 되는거 같다.?? 왜 이렇게 구현한 내용을 분석 못하겠고, 뭐가 뭔지 모르겠지 ㅠ

 

즉 저분이 한건 노드에서 역으로 나오면서 깊이를 확인할 수 있다면 , 내가 구현한건 들어간 깊이를 확인하는 셈이다.!!! 두 코드 구현의 차이를 잘 숙지하자 반드시

 

필수로 풀자! https://www.acmicpc.net/problem/17070    

17070번: 파이프 옮기기 1

 

 

 

 

1256번 사전

 

이 부분을 몰랐다.

 

위의 공식을 구하면 파스칼의 삼각형처럼 조합을 순차적으로 구할 수 있습니다.  당연히 중간 계산과정에서 숫자가 넘어가는 경우가 생깁니다.  아마 정답률이 낮은 이유 중에 숫자 범위를 벗어나서 고민한 사람들이 있을겁니다.  하지만 K값이 109109 이하로 주어지기 때문에 숫자값이 넘치는 경우에는 숫자를 제한시켜주면 됩니다.  속편하게 long long으로 처리한 사람들도 있었겠지만, 아마도 틀렸습니다가 나왔을겁니다.  K가 int 범위인데, 안 넘어갈거라고 생각했을 수도 있겠죠.  대충 계산해보면, 100C50≈1029100C50≈1029이니까요.

출처: https://sdev.tistory.com/499 [잡동사니 개발자의 블로그]