99클럽 코테 스터디 11일차 TIL - 84021 퍼즐 조각 채우기
84021. 퍼즐 조각 채우기 / c++ / level3 / 1시간+
문제 및 코드
접근 방식
그래프 탐색 / BFS / 구현
- 먼저 table 에서 블록(위치값의 벡터)들을 BFS 로 구한다.
- table을 탐색할 때, 좌상단부터 우하단 방향으로 탐색하기에, 블록의 첫 번째 부분은 항상 가장 위에 있고, 그 중 가장 왼쪽에 위치한다.
- 구한 블록을 첫 번째 부분 기준으로 다시 표현한다. (모든 칸에서 첫 번째 칸의 위치를 빼주면 됨, 이 때 첫 번째 부분이 1에서 설명한 것처럼 가장 작으므로 모든 값은 양수로 표시됨)
- 블록을 총 3번 회전시켜서 4개의 형태를 모두 구한다. (이 때는 블록의 x,y 좌표를 바꾸고, y 좌표에 -1을 곱해줌)
- 해당 블록들을 다시 정렬한다. (4번으로 인해 정렬이 틀어졌기 때문)
- 블록 구하기가 끝나면 이제 board에서 빈칸을 찾는다. (블록과 마찬가지로 위치값의 벡터로 구함)
- 빈칸이 구해지면, 3번에서처럼 빈칸을 첫 번째 부분을 기준으로 다시 표현한다.
- 그 후 빈칸을 정렬한다.
- 정렬된 빈칸을 블록 벡터를 순회하면서 맞는 블록이 있는지 찾는다. (이 때, usedBlock 이라는 bool 벡터를 하나 선언해서 블록의 재사용을 막는다. 또한 한 블록은 4개의 회전 형태를 모두 고려한다.)
- 맞는 블록이 있다면, usedBlock 에 해당 블록을 체크해주고, 블록의 칸 갯수를 answer에 더한다.
- 맞는 블록이 없다면, BFS에서 사용한 방문 정보를 초기화시킨다. (해당 빈칸을 다른 부분에서 다시 찾기 위함)
- 위의 과정으로 board를 모두 탐색하면 answer를 반환한다.
생각해 볼 점
- 이미 풀어봤던 문제임에도 시간이 꽤 걸렸다. 틀을 잡는건 금방 했는데, 블록을 탐색한 후 정렬을 언제 해줘야하는지가 많이 헷갈렸다. 문제를 정확하게 먼저 분석하고 풀었어야했는데, 또 바로 푸는 습관이 나와서 더 오래 걸렸던 것 같다.
- 게더타운에서 풀기 위해 밤 늦게 풀었더니 졸려서 머리가 더 안돌아갔던 것 같다.
해시태그
#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL