[백준] 12867 : N차원 여행

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

12867번: N차원 여행

---

• 딕셔너리 안에 딕셔너리를 넣으면 키값들만 저장되기 때문에, 상태 점검을 할 수가 없다.
• 그래서 굳이 딕셔너리로 존재하는지 검사하지 않고, M 이 최대 50개 이기 때문에 완전탐색으로 한 지점에 도착할 때 마다 리스트에 있는 모든 지점들에 대해 비교해줄 수 있다고 생각했다.
• 다만 N 차원이 최대 10억차원 까지 가능하기 떄문에 모든 차원에 대해 표현할 수 없으므로, 딕셔너리를 통해 움직인 차원에 대해서만 관리해준다.
• 어차피 이동 경로가 최대 50개이면 많아봤자 50차원까지만 표현 가능하기 때문에 충분히 가능하다.
• 딕셔너리를 통해 현재 위치의 상태를 나타내고, 리스트에 매번 추가해줌으로써 모든 이동 경로에 대해 관리할 수 있다.

---

N = int(input())
M = int(input())
dims = list(map(int, input().split()))
dir = input()

able = True
path = [{}]
cur = {}

for i in range(M):
    cur[dims[i]] = cur.get(dims[i], 0) + (1 if dir[i] == '+' else -1)
    if cur[dims[i]] == 0:               # 위치가 0 인 차원은 딕셔너리에서 제거함으로써 모든 차원 표현할 필요 없음)
        del cur[dims[i]]
    for cmp in path:
        if cur.items() == cmp.items():  # 지나왔던 경로에 현재 위치가 존재하면 불가능
            able = False
            break
    if not able:
        break
    path.append(cur.copy())             # 경로에 현재 위치 추가

if cur == {}: able = False      # 마지막이 원점일 경우에도 불가능
print(1 if able else 0)