BOJ 12867 - N차원 여행 (Python)

S2, 딕셔너리

문제

수빈이는 여행을 좋아한다. 더 이상 지구에서 여행할 곳이 없어진 수빈이는 N차원 우주로 여행을 떠났다. 우주의 각 점은 좌표 N개로 이루어 지며, 각각의 좌표는 1부터 N까지 인덱스가 매겨져 있다.

수빈이는 원점(모든 좌표가 0인 곳)에서 여행을 시작하며, 아래와 같은 방법으로 움직인다.

• 첫 번째로 움직일 좌표의 인덱스를 고른다. (1부터 N까지 중의 하나)
• 그 다음, 그 좌표의 값을 1만큼 증가시킨 곳이나 감소시킨 곳으로 이동한다. (다른 좌표는 이동하기 전과 같아야 한다)
  수빈이는 여행을 떠나기 전에 여행 계획을 작성해 놓았고, 같은 점을 두 번 이상 방문하는지 아닌지 알아보려고 한다.

수빈이가 여행 계획에서 고른 좌표 인덱스와, 좌표가 증가하는 방향으로 이동했는지, 감소하는 방향으로 이동했는지가 주어진다. 수빈이가 첫 번째 점과 마지막 점을 포함한 모든 점을 중복해서 방문하지 않게 방문할 수 있다면 1을, 아니면 0을 구하는 프로그램을 작성하시오.

풀이

1. set()을 통해 이동 과정을 담아 이를 비교해나가며 풀었다.

• TC는 통과했는데, 메모리 초과에 걸렸다.
  제한조건을 보니, N이 무려 10억...

from sys import stdin

n = int(stdin.readline())
start = [0]*n
m = int(stdin.readline())
travel = list(map(int, stdin.readline().split()))
op = list(map(str, stdin.readline().rstrip()))

route = set()
route.add(tuple(start))

now = start
for i in range(m):
    idx = travel[i] - 1
    if op[i] == '+':
        now[idx] += 1
    else:
        now[idx] -= 1
    if tuple(now) not in route:
        route.add(tuple(now))
    else:
        print(0)
        exit()

print(1)

2. 구글링 참조 → 딕셔너리 사용

• {"좌표" : "값"} 을 통해 이를 표현할 수 있다.
  

from sys import stdin

n = int(stdin.readline())
m = int(stdin.readline())
travel = list(map(int, stdin.readline().split()))
op = list(map(str, stdin.readline().rstrip()))

flag = True
path = [{}]
now = dict()

for i in range(m):
    now[travel[i]] = now.get(travel[i],0) + (1 if op[i] == '+' else -1)

    if now[travel[i]] == 0:
        del now[travel[i]]

    for cmp in path:
        if now.items() == cmp.items():
            print(0)
            exit()

    path.append(now.copy())

if now == {}:
    print(0)
else:
    print(1)

참... 생각하기 어렵다...