소프티어

소프티어 Garage game (Python)

N x N 배열을 클러스터링할 때는 BFS를 사용했고 클러스터를 선택하는 탐색은 DFS를 사용했습니다. 3N줄에 걸쳐 입력되는 값을 열단위로 저장해 사용하면 자동차를 떨어뜨리는 로직을 구현하는데 매우 편해집니다.특히, 39번, 40번 테스트케이스에서 시간초과가 잘 발생하는데, 해설강의(https://www.youtube.com/watch?v=K4TWAtHuRNw)로부터 힌트를 얻었습니다. 아래 코드에선 near_same_color라는 함수를 추가하여 BFS 코드에서 사이즈가 1인 경우를 스킵하여 TLE를 피할 수 있었습니다. 제 생각으로는 BFS에서 적어도 한 번은 4번의 방향을 탐색해야 하는데 클러스터 사이즈가 1인 부분이 많은 경우 오버헤드가 되어버리는 이유가 아닐까 싶습니다.