1. 공부한 내용

문제1 - 99 클럽 - 방의 개수:

[ 문제 풀이 ]

문제는 다음과 같다. 이동 가능한 경우의 수는 좌측과 같이 7개이며, list로 움직여야 할 방향이 순차적으로 주어진다. 이 때, 모든 경로를 움직인 후, 사방이 막혀 있는 방의 갯수를 구하는 문제이다.

나는 관성에 따라 그래프에 표현하면서 접근하였으며, 방을 구성하는지 파악하기 위해 그래프를 2배 스케일링하여 표현하였다. 여기까지는 좋은 시도였으나 그래프를 2배 스케일링하여 다루더라도 각 포인트만을 체크하는 방법은 위와 같은 경우를 파악할 수 없다.

⇒ 따라서 꼭짓점과 선을 체크해줘야 하는게 이 문제의 핵심이다.

실제 정답 풀이1 - 오일러 공식 활용하기

1. 주어진 이동 단위를 1이 아닌 2로 취급하되, 1칸씩 움직이며 체크한다. (내가 그래프를 2배 스케일링 하여 체크한 점과 동일함)

2. for문을 통해 주어진 arrows 리스트를 조회하고, next point와 mid point(pre와 next 사이)를 조회한다.

3. set을 활용해 unique한 포인트의 갯수를 count한다. - mid_point와 next_point 둘다

4. set을 활용해 unique한 선분의 갯수를 count한다.

line.add((pre_point,mid_point))
line.add((mid_point,pre_point))
line.add((mid_point,next_point))
line.add((next_point,mid_point))