99클럽 코테 스터디 13일차 TIL - 87964 아이템 줍기

87964. 아이템 줍기 / c++ / level3 / 1시간+

문제 및 코드

접근 방식

그래프 탐색 / BFS

1. 점이 겹치는 뭉치는 문제를 해결하기 위해 사각형의 각 좌표를 * 2 해줌
2. 사각형을 돌면서 2차원 bool 배열 map에 테두리를 true 표시해줌
3. 다시 사각형을 돌면서 사각형 안쪽을 false로 바꿔줌
4. 해당 map을 기준으로 BFS 진행 (이 때, 시작 좌표도 각각 *2)
5. 마지막으로 item 좌표 * 2 한 위치의 비용값의 절반을 return

생각해 볼 점

1. 사각형들의 테두리를 잇는 부분은 크게 어렵지 않았다.
2. 그런데 좌표가 1단위로 나눠져서, 분명 이어져있지 않은 길인데도 bfs할 때 이어진 것처럼 작동하는 문제가 있었다.
3. 예전에 이걸 *2해서 (지도가 커지면 좌표가 더 세밀해지는 느낌) 해결했던 경험이 있었는데, 이걸 다시 생각해내기까지가 정말 오래 걸렸다.
4. 다음에는 지금처럼 좌표값을 더 세분화해야 할 때, * 2 하는 방법을 바로 기억해낼 수 있도록 해야겠다.

해시태그

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