날짜: 2022년 1월 31일 오후 5:51

코드

Algorithm/49190.py at main · Junroot/Algorithm

풀이

내 풀이

선을 그으면서 도형이 언제 생기는지 생각해보면 된다. 답은 기존에 그어져있던 선과 만나는 순간에 방이 하나 늘어난다. 그럼 선이 만나는 순간이 언제인지를 고려해보면 된다.

  1. 새로운 선을 그으면서, 기존에 방문한 점으로 이동하는 경우
  2. 새로운 선을 그으면서, 대각선을 그을 때 맞은 편 대각선이 이미 그어져 있는 경우

이 두 가지의 상황만 고려해서 시뮬레이션 하면 쉽게 해결이 가능하다.

다른 사람 풀이

다른 사람 풀이를 봤는데 너무 좋은 풀이법이 있어서 가져왔다. 오일러 공식을 사용하는 방법이다.

2차원에서는 v - e + f = 1 이다.

v = (꼭짓점의 개수), e = (모서리의 개수), f = (면의 개수)

어차피 방의 모양이 아니라 개수만 구하면 되기 때문에 지나가는 모든 점들을 다각형의 꼭짓점으로 생각하고 문제를 풀면 쉽게 해결할 수 있다. 이 때, 대각선이 교차하는 경우를 세기 쉽게 하기위해 이동하는 길이를 2씩 늘여서 계산하면 수월해진다.


def solution(arrows):
    point=set([(0,0)])
    line=set()
    move=[[0,2],[2,2],[2,0],[2,-2],[0,-2],[-2,-2],[-2,0],[-2,2]]
    pre_point=(0,0)
    for A in arrows:
        next_point=(pre_point[0]+move[A][0],  pre_point[1]+move[A][1] )
        mid_point=(pre_point[0]+move[A][0]//2,  pre_point[1]+move[A][1]//2 )
        point.add(next_point)
        point.add(mid_point)
        line.add((pre_point,mid_point))
        line.add((mid_point,pre_point))
        line.add((mid_point,next_point))
        line.add((next_point,mid_point))
        pre_point=next_point
    answer = len(line)//2-len(point)+1
    return answer if answer>=0 else 0