[백준] 15886번: 내 선물을 받아줘 2

요즘... 생각이 많아 잠시 휴식 타임을ㅠㅠ 여튼 지금부터 다시 힘내보려 합니다!

 

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

15886번: 내 선물을 받아줘 2

이 문제를 처음 접했을 때 무슨 소리인지 이해하는데 한참 걸렸다.

구사과의 위치를 모르지 이동을 시작하는 위치와 관계없이 선물을 줘야한다. 문제에서 이동은 E와 W인 경우에 이동한다.

그렇다면 결론은 E에서 W로 바뀌는 즉 이동이 바뀌는 순간 E에 선물을 놓는다면 구사과를 무조건 얻을 수 밖에 없다.

이렇게 바뀌는 경우에만 놓는다면 최소의 경우의 수가 나오게 된다.

 

초기 map은 0으로 세팅해둔다. 그리고 지나간 길은 1로 바꾸고 이때 아직 방문하지 않았는데 'E'인 길이면 거기에 사과를 놓으니 이때 카운팅을 해준다.

#include<iostream>
#include<vector>

#define FastIO ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

using namespace std;

vector<int> map;
string sInput;

void DFS(int start)
{
	if ( map[start] == 1 )
		return;
	map[start] = 1;

	if ( sInput[start] == 'E' )
		DFS(start + 1);
	else
		DFS(start - 1);
}

int main(void)
{
	FastIO;

	int N = 0; // 골목길의 길이 N
	cin >> N;
	cin >> sInput;
	map.resize(N, 0);
	int answer = 0;
	for ( int i = 0; i < sInput.length(); i++ )
	{
		if ( map[i] != 1 && sInput[i] == 'E' )
		{
			DFS(i);
			answer++;
		}
	}

	cout << answer << "\n";
	return 0;
}