99클럽 코테 스터디 24일차 TIL - 49190 방의 개수

49190. 방의 개수 / c++ / level5 / 2시간+

문제 및 코드

접근 방식

그래프

1. 방을 만드는 조건을 찾아야했다.
   1. 이미 방문한 좌표를 다시 방문할 때 방이 생성됐다.
   2. 방문한적 없는 간선(arrow)로 방문해야 방이 생성됐다.
2. unordered_set으로 좌표와 간선의 방문여부를 체크했고, 테스트 케이스를 통과했지만, 문제는 틀렸다.
3. 아무리 생각해도 이유를 알 수 없어서, 다른 분들의 접근 방법을 찾아봤다.
4. 점 4개를 모래시계 형태로 교차해서 지나가게 되면, 이론상 방이 1개 생성되어야 하지만, 실제로는 방이 2개가 생성됐다.
5. 좌표 문제에서 가끔 나오는, 정밀도의 문제 (내가 이름지은..) 였다.
6. 이 문제의 해결법은 좌표계 자체를 2배씩 키우고, 한번 하던 이동을 2번으로 바꿔주는 것이었다.
7. arrows의 각 원소를 2번씩으로 늘린, newArrows를 만들고, 이전까지의 로직을 newArrows를 기반으로 실행했더니 통과했다.

생각해 볼 점

1. level5문제는 아마 이번이 처음 푼 것 같다.
2. 이쯤오니 문제가 정확히 요구하는 바가 무엇인지 안에 숨어있는 원리를 찾아내는게 정말 중요하게 느껴졌다.
3. 특히 좌표계가 나오면 항상 정밀도 문제를 생각해봐야겠다. (와 모래시계 모양으로 꽈서 연결하는건 정말 생각하지 못했다…)

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL