어흥

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

알고리즘/백준

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

라이언납시오 2020. 5. 3. 15:44
728x90
반응형

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

 

15886번: 내 선물을 받아줘 2

욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직사각형 지도로 나타낼 수 있으며, 1×1크기의 정사각형으로 나누어져 있다. 구사과의 위치는 (1, x)로 나타낼 수 있으며, (1, x)는 왼쪽에서부터 x번째 칸을 의미한다. 지도의 각 칸에는 E, W중의 한 문자가 쓰여져 있는데, 구사과는 이 문자를 이용해서 이동한

www.acmicpc.net

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;
}
728x90
반응형
Comments