문 만들기

농부 존은 농장의 일부를 둘러싸는 새 울타리를 짓기로 했지만, 계속 딴생각을 하다가 결국 의도했던 것보다 훨씬 이상한 모양의 울타리를 짓고 말았다!

구체적으로, 농부 존은 위치 \((0,0)\)에서 시작해 \(N\)번의 걸음을 걷는데, 각 걸음은 북, 남, 동, 서 중 한 방향으로 한 단위 거리씩 이동한다. 한 걸음 걸을 때마다 그는 자기 뒤에 한 단위 길이의 울타리를 설치한다. 예를 들어 첫 걸음이 북쪽이라면 \((0,0)\)에서 \((0,1)\)까지의 울타리 구간이 추가된다. 농부 존은 같은 지점을 여러 번 지날 수도 있고, 같은 울타리 구간을 여러 번 설치할 수도 있다. 이미 지어 놓은 울타리 구간을 경로가 가로지르면 울타리가 스스로 교차할 수도 있다.

말할 것도 없이, 농부 존은 울타리를 완성한 뒤 그 결과에 크게 낙담했다. 특히, 농장의 일부 영역이 다른 영역과 분리되어, 울타리를 넘지 않고는 한 영역에서 다른 영역으로 걸어갈 수 없게 되었을 수도 있다는 것을 알게 되었다. 농부 존은 이 문제를 해결하기 위해 울타리에 문을 달고 싶다. 문은 그가 설치한 임의의 단위 길이 울타리 구간에 달 수 있으며, 그 구간의 양쪽을 오갈 수 있게 해 준다.

농장의 모든 영역이 다시 서로 오갈 수 있게 되도록 농부 존이 만들어야 하는 문의 최소 개수를 구하여라.

출제자: Brian Dean

출제자: Brian Dean

입력의 첫째 줄에 \(N\) (\(1 \leq N \leq 1000\))이 주어진다. 다음 줄에 농부 존의 경로를 나타내는 길이 \(N\)의 문자열이 주어진다. 각 문자는 N(북), E(동), S(남), W(서) 중 하나이다.

농장의 모든 영역의 연결성을 복원하기 위해 농부 존이 만들어야 하는 문의 최소 개수를 하나의 정수로 출력한다. 농장이 처음부터 연결되어 있다면 답이 0일 수도 있음에 유의하자.

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > January > Silver