[BOJ/1103] 게임, c++

 

🔗 링크

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

1103번: 게임

https://github.com/jokj624/PS/blob/master/1000-5000/1103.cpp

jokj624/PS

🤯 한줄 후기

코드 순서 조심하자 😭

🤷 문제

👩‍💻 풀이

아픈 기억

굉장히 많이 틀렸다. 대회 준비 스터디 Algospecial 첫 만남때 풀었던 문제인데 문제를 읽고 셋 다 그냥 풀어보자고 했다.

딱히 큰 접근 방식이 필요한 것 같진 않았고, 문제에서 요구하는 방식대로 dfs 코드만 구현해주면 될 것 같았다.

동전이 무한대로 움직인다는 것은 결국 한번 방문했던 곳에 또 한번 방문하는 것이랑 같으므로 그렇게 판단해주면 된다.

결과적으로 나말고 다른 친구가 먼저 구현해서 제출했지만 아마 TLE 가 났던 것 같다! 

 

분류를 한번 열어보기로 했다.

내가 제일 못하는 dp

DP를 써서 푸는 문제였다 .. . 내가 정말 싫어하는 류의 문제

 

점화식을 생각해봤는데 dp[x][y] = x, y 위치 까지 오는데 동전이 움직일 수 있는 최대 횟수 정도로 생각하기로 했다. 

해당 위치에 이미 동전 횟수가 저장되어 있다면 더 이상 탐색하지 않고 바로 반환하여 시간을 줄일 수 있을 것 같았다.

 

동전이 해당 위치에 적힌 숫자만큼 움직여야 하기 때문에 nextx, nexty 좌표를 구할 때, 

dx[i] * map[x][y]-'0', dy[i] * map[x][y]-'0' 이런 식으로 구현했다.

if(x < 0 || y < 0 || x >= N || y >= M)	return 0;  // 경계선 밖으로 나갔을 경우 탐색 종료
	if(map[x][y] == 'H')	return 0;    // 구멍에 빠졌다면 해당 탐색 종료
	if(visit[x][y]){
		printf("-1");   //한번 방문한 곳 재방문 시 무한대로 도는 것이므로 -1 출력 후 종료
		exit(0);
	}
	if(dp[x][y])	return dp[x][y];   // 이미 dp 메모이제이션 되어있다면 반환
	visit[x][y] = true;  // 방문 기록
	for(int i=0; i<4; i++){
		int nx = x + dx[i]*(map[x][y]-'0');
		int ny = y + dy[i]*(map[x][y]-'0');   // 현재 좌표에서 갈 수 있는 좌표 구하기
		dp[x][y] = max(dp[x][y], dfs(nx, ny)+1); // 현재 dp값, 새로운 좌표 dp값 + 1 중 max 값 갱신
	}
	visit[x][y] = false;  // 다음 탐색을 위해 방문 기록 수정 
	return dp[x][y];  // 출력

탐색 풀이는 주석을 참고하시길!

 

아, 계속 틀렸던 이유가 뭐였냐면

if(dp[x][y])	return dp[x][y];
if(visit[x][y]){
	printf("-1");
	exit(0);
}

바로 이 순서 때문이다. 

무한대로 동전이 도는 것을 먼저 체크하지 않고, dp값 반환부터 체크해버려서 무한대로 돌때도 dp값을 먼저 반환해버렸다.

이걸 찾느라 엄청나게 틀렸었다 😇 

💻 코드

//AC
//BOJ 1103 게임
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
string map[105];
int dp[105][105];
bool visit[105][105];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int N, M;
int dfs(int x, int y){
	if(x < 0 || y < 0 || x >= N || y >= M)	return 0;
	if(map[x][y] == 'H')	return 0;
	if(visit[x][y]){
		printf("-1");
		exit(0);
	}
	if(dp[x][y])	return dp[x][y];
	visit[x][y] = true;
	for(int i=0; i<4; i++){
		int nx = x + dx[i]*(map[x][y]-'0');
		int ny = y + dy[i]*(map[x][y]-'0');
		dp[x][y] = max(dp[x][y], dfs(nx, ny)+1);
	}
	visit[x][y] = false;
	return dp[x][y];
}
int main(){
	cin >> N >> M;
	for(int i=0; i<N; i++){
		cin >> map[i];
	}
	cout << dfs(0, 0);
	return 0;
}