백준 1103 - 게임(C++, 복습)

문제 링크입니다 https://www.acmicpc.net/problem/1103

1103번: 게임

DFS +DP를 이용하면 풀 수 있는 문제였습니다.

문제 조건

출력 예시

무한번 움직일 수 있는 경우, 모든 선택지마다 값을 새로 찾는 경우 -> 시간 초과가 생긴다!

따라서 해당 칸에서 움직일 수 있는 최대 횟수, 이미 왔던 곳에 다시 왔다면 무한이라고 처리해야하는 문제입니다!

 

문제 접근 방법

1. char배열로 값을 입력 받은뒤 int형 배열에다가 옮긴다. (H는 0으로 옮겼습니다)

2. dfs탐색을 (1,1)부터 시작한다.

3. 보드에서 탈출했을 경우 -> 0

   이전에 방문했었던 곳인 경우 -> cant 배열을 true로 만든다.

   해당 좌표에서 움직일 수 있는 최댓값이 있는 경우 -> 그 값을 return 한다.

4. 보드에 적힌 값만큼, 상하좌우로 움직인다.

5. answer 변수에 dfs()의 값을 받는다.

 

 

문제 접근 방법 - 2번+3번+4번

int dfs(int x, int y) {
	if (cant) return 0;
	if (x < 1 || y < 1 || x > N || y > M || map[x][y] == 0) {
		return 0;
	}
	if (check[x][y] == 1) {
		cant = true;
		return 0 ;
	}
	if (dp[x][y] != -1) {
		return dp[x][y];
	}
	check[x][y] = 1;
	dp[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		int xx = x + (map[x][y] * dx[i]);
		int yy = y + (map[x][y] * dy[i]);
		dp[x][y] = max(dp[x][y], dfs(xx, yy) + 1);
	}
	check[x][y] = 0;
	return dp[x][y];
}

1. cant 변수는 무한번 돌 수 있는지의 여부를 확인해주는 역할을 합니다.

   cant가 true라면 무한번 돌 수 있다는 의미임으로 계속 return 했습니다.

2. 이미 이전에 방문했던 곳? -> 이 경우에는 무한번 돌 수 있습니다. 따라서 이때 cant를 true로 만들었습니다.

3. dp배열에 지금 좌표의 값이 있다면? -> 이전 탐색 중에서 해당 좌표에 도착했을 경우 움직일 수 있는 최댓값을 저장     한 상태입니다. 따라서 해당 값을 return 합니다.

4. 상하좌우로 현재 좌표의 값만큼 움직인 후, 값을 dfs에 넣어줍니다.

 

 

문제 해결 방법 - 5번

void solve() {
	memset(dp, -1, sizeof(dp));
	int answer = dfs(1, 1);
	if (cant) cout << -1;
	else cout << answer;
}

cant가 true 인 경우 -> -1를 출력

아닌 경우 answer의 값을 출력했습니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define MAX 100001
using namespace std;

int N, M;
char board[51][51];
bool cant = false;
int map[51][51];
int check[51][51];
int dp[51][51];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };



int dfs(int x, int y) {
	if (cant) return 0;
	if (x < 1 || y < 1 || x > N || y > M || map[x][y] == 0) {
		return 0;
	}
	if (check[x][y] == 1) {
		cant = true;
		return 0 ;
	}
	if (dp[x][y] != -1) {
		return dp[x][y];
	}
	check[x][y] = 1;
	dp[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		int xx = x + (map[x][y] * dx[i]);
		int yy = y + (map[x][y] * dy[i]);
		dp[x][y] = max(dp[x][y], dfs(xx, yy) + 1);
	}
	check[x][y] = 0;
	return dp[x][y];
}

void solve() {
	memset(dp, -1, sizeof(dp));
	int answer = dfs(1, 1);
	if (cant) cout << -1;
	else cout << answer;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> board[i][j];
			if (board[i][j] == 'H') map[i][j] = 0;
			else map[i][j] = board[i][j] - '0';
		}
	}
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!