[백준 C++]1103번: 게임

1.문제

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

1. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
3. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

2. Solved.ac 난이도

3. 활용 알고리즘: BFS->DFS->DFS+DP

4. 틀린 이유: 반례 고려X, 알고리즘 잘못 선택

 

 

 

시도1. (WA)

BFS로 경로/ 거리 구할때 자꾸 result++; 이런식으로 올리려하는데, 안됨ㅠㅡㅠㅠ 바로 전 경로에 저장해놓은 거리보다 +해야하는거 잊지 말아야함.

 

 

시도2 (WA)

한번 거쳐간점을 다시 갔다고 무조건 사이클이 있는 것이 아님.

indioindio  님 반례

4 3 133 5HH HHH 21H 이런 경우를 생각해보시면 1 - 5를 방문하고 끝난 후에, 1 - 3 - 1 - 2 - 5의 경로를 갈 때 5를 다시 방문하게 되어 사이클이라고 인식하게 됩니다. (물론 방문순서에 따라서 visit[tx][ty]<=result 때문에 -1을 출력하지 않을 수도 있지만 visit[tx][ty] <= result를 통과하는 이런 케이스가 충분히 있다고 생각됩니다.)

 

시도3 (WA)

BFS는 거쳐간 점들을 한 경로당으로 계산하기가 어려움!

그렇다고 경로를 죄다 저장하면서, 해당 정점이 해당 경로에 저장되어있는지를 확인하는 방법을 사용하기엔 너무 비효율적임 따라서 결국 DFS를 사용해야하는 문제이더라...

 

시도3(TLE)

BFS로 바꿔 계산하였으나 타임리밋..

재귀를 구현하면서 return result+1;로 재귀를 나올때마다 1씩 증가하고, 한 함수 안에서의 반복 재귀 결과중에서는 더 큰값을 리턴해주는 방법 사용. 그러다보니 모든 정점을 한번씩 방문하므로, 타임리밋이 걸린 것 이다. 따라서 최대 경로를 아는 정점에 대해서는 그 값을 저장해주는 DP방식 적용 필요.

 

 

 

최종 정답 코드

#include<iostream>
#include<queue>
using namespace std;

int board[51][51];
bool visit[51][51];
int range[51][51];
int ud[] = { 1,-1,0,0 };
int lr[] = { 0,0,1,-1 };
int n, m;

int dfs(int i,int j) {
	int result = 0;
	int now = board[i][j];
	visit[i][j] = true;
	for (int k = 0; k < 4; k++) {
		int ii = i + now * ud[k];
		int jj = j + now * lr[k];
		if (n > ii && ii >= 0 && m > jj && jj >= 0&&board[ii][jj] != 'H' - '0') {
			if (visit[ii][jj] == false) {
				int a;
                //DP 이용하는 부분
				if (range[ii][jj] != 0) {
					a= range[ii][jj];
				}
				else {
					a = dfs(ii, jj);
				}
				if (a == -1) {
					return -1;
				}
				if (result < a) {
					result = a;
				}
			}
			else {
				return -1;
			}
		}
	}
	range[i][j] = result+1;
	visit[i][j] = false;
	return result+1;
}

int main() {
	cin >> n >> m;
	string row;
	for (int i = 0; i < n; i++) {
		cin >> row;
		for (int j = 0; j < m; j++) {
			board[i][j] = row[j] - '0';
		}
	}
	cout<<dfs(0,0);
	

	return 0;
}