[백준 15886] 내 선물을 받아줘 2 (C++)

문제 링크: https://www.acmicpc.net/problem/15886

15886번: 내 선물을 받아줘 2

1. 주의할 점

- 메모아이징을 사용한 DFS를 이용한다 (DP문제)

 

2. 구현

- Check[] 배열을 전부 -1로 초기화 한다

- 0~Num-1 까지 For문을 돌며 Check값이 -1이라면(아직 방문한 적이 없다면) DFS(int Idx, int Cnt)를 수행한다

- DFS(int Idx, int Cnt)는 Int형 함수로 return 값이 필요하다

- 우선 Check[Idx]값이 -1이 아니라면 Check[Idx] 값을 반환한다

- -1이라면 Check값을 Cnt로 설정하여 -1과는 차별화게 되게 현재 방문하고 있다는 표시를 남긴다

- 가장 왼쪽 칸이 W인 경우와 가장 오른쪽 칸이 E인 경우는 따로 예외처리를 한다

- Temp변수에 다음 이동해야 하는 칸에 대한 Return값을 돌려받고, Check[Idx] 값을 다시 Temp로 갱신한다

- For문이 종료 된후, 사용된 숫자가 몇 개인지 확인하고 출력한다

 

#include <iostream>
#include <algorithm>
using namespace std;
char arr[1000];
int check[1000], num, result = 0;
bool number[1001] = { false, };
int dfs(int idx, int cnt) {
	if (check[idx] != -1) return check[idx];
	int temp = check[idx];
	check[idx] = cnt;
	if (arr[idx] == 'E') {
		if (idx + 1 == num) return cnt;
		else
			temp = dfs(idx + 1, cnt);
	}
	else if (arr[idx] == 'W') {
		if (idx == 0) return cnt;
		else
			temp = dfs(idx - 1, cnt);
	}
	check[idx] = temp;
	return temp;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num;
	int vv = 0;
	for (int i = 0; i < num; i++)
		cin >> arr[i];
	for (int i = 0; i < num; i++)
		check[i] = -1;
	for (int i = 0; i < num; i++)
		if (check[i] == -1) 
			dfs(i, ++vv);	
	for (int i = 0; i < num; i++) {
		if (!number[check[i]]) {
			number[check[i]] = true;
			result++;
		}
	}		
	cout << result;
	system("pause");
	return 0;
}