arrow의 최대 길이는 100,000이므로, 직접 좌표를 찍어가며 브루트포스로 풀면 공간복잡도가 매우 커질 수 있다(대각선 이동이 가능하므로 최대 100,000^2 이 가능하다)
그런데 생각해보면, 닫힌 공간이 되려면 이미 방문했던 점에 다시 도달해야 한다는 조건이 있다. 따라서 단 한번의 순회 안에, 방문한 좌표들을 저장해가며 이미 방문했던 좌표에 도달하는 순간마다 1을 카운트해주면 된다.
또한, 대각선 방향의 이동을 생각해 볼 수 있다. 다음 예시를 보자.
다음 예시를 보자. 총 세번의 이동, 그리고 교차하는 대각선과 남은 한 변이 삼각형을 이룸에도, 방문한 점과 한 번도 만나지 않았기 때문에 총 결과는 0을 도출한다. 이를 방지하기 위해, Arrows를 두 번씩 이동해주는 방법을 사용하자.
또한 방문 좌표뿐 아니라 생성한 선 역시 저장해야 한다는 조건이 붙는다. 이미 방문한 선을 다시 방문하거나, 다시 이전의 점으로 되돌아가는 등의 상황을 처리하기 위함이다. 나의 풀이의 경우 Set을 이용하여 edge와 coord를 같이 저장하였다.(Set을 arrows의 원소마다 참조해야 하기 때문이며 Set의 Find는 O(1)의 시간이 소요되기 때문이다.)
풀이 코드
dx = [0, 1, 1, 1, 0, -1, -1, -1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
def solution(arrows):
answer = 0
x, y = 0, 0
edge_set = set()
coord_set = set([(x, y)])
for arrow in arrows :
for _ in range(2) :
ax, ay = x + dx[arrow], y + dy[arrow]
if (ax, ay) in coord_set and (x, y, ax, ay) not in edge_set :
answer += 1
coord_set.add((ax, ay))
edge_set.add((x, y, ax, ay))
edge_set.add((ax, ay, x, y))
x, y = ax, ay
return answer
