백준 - 1103 게임

문제

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

1103번: 게임

게임을 진행하면서 움직일 수 있는 동전의 최대 횟수를 구하는 문제였다.

 

문제 풀이

많은 시행착오가 있었고, 결국 다른 블로그를 참고해서 해결했다.

 

처음에는 단순히 백트래킹을 이용했는데, 6%에서 시간 초과가 나타났다. 이를 해결하기 위해서 좌표와 횟수, 방향 정보를 우선순위 큐에 넣어 bfs를 돌렸는데 해결되지 않는 경우가 있었다. 그리고 map의 각 칸에 set을 만들어 이전에 방문한 적이 있는지를 판단하도록 했는데 1%에서 틀렸다고 했다. dp를 사용해야 할 것 같긴 한데 어떻게 사용해야 할지 모르겠어서 다른 블로그를 참고했는데 생각보다 너무 간단해서 놀랐다.

 

dfs에 인자로 넘겨주던 cnt를 dp로 관리하고, 중간에 갱신되지 않을 때에는 dfs를 돌리지 않게 해 탐색 횟수를 줄여서 해결 가능했다. 이번 문제는 혼자서 풀지 못했지만 앞으로 이런 유형의 문제는 풀 수 있을 것 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string>

using namespace std;

typedef struct info {
	int x;
	int y;
	int cnt;
	int dir;
}info;

int N, M;
vector<vector<int>> map;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
bool isInf = false;

vector<vector<bool>> visit;
vector<vector<int>> dp;
int maxCnt = 0;

bool isInside(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < M) return true;
	return false;
}

void dfs(int x, int y) {
	if (isInf) return;

	//printf("%d %d cnt: %d\n", x, y, cnt);
	maxCnt = max(maxCnt, dp[x][y]);

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i] * map[x][y];
		int ny = y + dy[i] * map[x][y];

		if (isInside(nx, ny) && map[nx][ny] != -1) {
			//현재 칸을 이전에 방문했는지 체크		
			if (!visit[nx][ny]) { //방문 전
				if (dp[nx][ny] >= dp[x][y] + 1) continue; //갱신 안되는 상황 -> 탐색 x
				visit[nx][ny] = true;
				dp[nx][ny] = dp[x][y]+1;
				dfs(nx, ny);
				visit[nx][ny] = false;
			}
			else {
				isInf = true;
				return;
			}			
		}
	}
}

int main() {

	scanf("%d %d", &N, &M);

	map = vector<vector<int>>(N, vector<int>(M));
	dp = vector<vector<int>>(N, vector<int>(M, -1));
	visit = vector<vector<bool>>(N, vector<bool>(M, false));			

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < M; j++) {

			if (str[j] >= '0' && str[j] <= '9') map[i][j] = str[j] - '0';
			else map[i][j] = -1;			
		}
	}

	dp[0][0] = 1;
	dfs(0, 0);

	if (isInf) printf("-1");
	else printf("%d", maxCnt);

	return 0;
}

/*

*/