[백준 15886번] 파이썬 - 내 선물을 받아줘2

백준 15886 - 내 선물을 받아줘2

시간 제한 2초, 메모리 제한 256MB

# 조건

• 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물을 전달해주려고 한다.
• 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다.
• 구사과가 있는 곳은 1×N 크기의 직사각형 지도로 나타낼 수 있으며, 1×1크기의 정사각형으로 나누어져 있다.
• 구사과의 위치는 (1, x)로 나타낼 수 있으며, (1, x)는 왼쪽에서부터 x번째 칸을 의미한다.
• 지도의 각 칸에는 E, W중의 한 문자가 쓰여져 있는데, 구사과는 이 문자를 이용해서 이동한다.
• 구사과의 위치가 (1, x)인 경우에 E가 쓰여져 있는 칸에 서 있었다면, (1, x+1)로, W의 경우에는 (1, x-1)로 순간이동한다.
• 구사과는 지치지 않기 때문에, 계속해서 이동한다.
• 욱제는 구사과의 위치를 모르기 때문에, 구사과가 이동을 시작하는 위치와 관계없이 선물을 주는 방법을 알아내려고 한다.
• 최소 몇 개의 칸 위에 선물을 놓으면, 구사과가 항상 선물을 가져가는지 구하는 프로그램을 작성하시오.
• 선물이 놓여진 칸에 구사과가 이동하면, 구사과는 항상 선물을 가져간다.

입력

• 첫째 줄에 골목길의 길이 N이 주어진다. (2 ≤ N ≤ 1,000)
• 둘째 줄에 길이 N짜리 구사과가 있는 곳의 지도가 주어진다.
• 지도에 쓰여 있는대로 이동했을 때, 지도를 벗어나는 경우는 없다.

출력

• 첫째 줄에 최소 몇 개의 칸에 선물을 놓아야 하는지 출력한다.

# 접근 방법

• 이동하는 방법은 앞으로 한 칸 또는 뒤로 한 칸이고 지도를 벗어나는 경우가 없다.
• 따라서, VISITED 배열을 생성해주고 0번부터 출발하며 방문하는 곳을 True로 변경해준다.
• 만약 돌아와서 True인 곳에 도착했다면 visted가 False인 곳을 찾아 다시 위 로직을 수행하면 된다.
• 또한 탐색 중에 출발지 외에 False를 한 번이라도 만난다면 cnt += 1을 해주면 된다.
• 또는 bfs를 이용해서 그룹의 개수를 탐색해주는 것도 하나의 방법이다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
words = input().strip()  
result = 0  
visited = [False] * N  
for i in range(N):  
    if not visited[i]:  
        idx = i  
        visited[i] = True  
        flag = False  
        while True:  
            if words[idx] == 'E':  
                idx += 1  
            else:  
                idx -= 1  
            if idx >= len(words) or visited[idx]:  
                break  
            else:  
                visited[idx] = True  
                flag = True  
        if flag:  
            result += 1  
print(result)