BFS

풀이 방법을 떠올리다가 처음에는 배열을 사용한 DP로 시도했는데, N이 10^18까지 가능해 배열로는 풀 수가 없는 문제였다. N이 워낙 크다보니 BFS로도 풀지 못할 것이라 생각해 시도조차 하지 않았었고 도저히 모르겠어서 알고리즘을 확인했는데 BFS가 있어서 놀랐다. 결국 BFS가 돌아갈 수 있었던 이유는 메모리가 1024byte로 모든 수를 메모이제이션 하기에는 부족하지만, BFS 큐 사이즈를 감당하기에는 충분했기 때문인 것 같다. BFS 특성상 모든 수를 다 돌아보지 않고 가장 빨리 도달하는 경우만 살펴보기 때문이다. 관건은 "-1연산을 최소화할 수 있는가?"인 것 같다.BFS 풀이추가적으로 새로 알았던 점은 defaultdict를 사용할 때 그동안 관습적으로 int를 넣어줬었는데 여기에 커스텀 메..

건물에 완전히 전파되기까지 시간이 걸려서 굉장히 까다로운 문제였다.건물이 완전히 전파되기까지는 방문처리를 하면 안되고, 완전히 전파되면 인접 구역으로 전파된다는 점이 고민을 많이 하게했던 문제같다.풀이 고민처음에는 큐에 (전파까지 남은 시간, y좌표, x좌표)의 형태로 관리하려고 했다. 만약 건물이라면 Tb의 시간을 넣고 이후 큐에서 빼고 1씩 감소시킨 뒤 다시 넣어줬고, 건물이 아니라면 0의 시간을 넣었다. 그래서 남은 시간이 0인 경우에만 인접 좌표로 전파시키도록 했는데, 아마 넣었다 빼는 과정에서 시간 초과가 난 것 같다. 그 뒤에는 방문 처리를 3차원 배열을 통해서 수행해보려고 했다. 건물이 Tb의 시간 이후에는 모든 층에 퍼지게 되므로 Tb의 층을 가진다고 볼 수 있다.이렇게 v[Tb][y좌표]..

1938 : 통나무 옮기기 처음에 계속 메모리 초과가 났는데 다시 생각해보면 회전 로직에서 시간 초과가 났던 것 같다.회전 시 통나무의 중심축을 제외한 두 좌표에 대해 y값과 x값이 바뀐다고 생각을 했었다.. 그렇게 생각하니 아래와 같이 정렬을 해줘야 했고 불필요한 리스트를와 패킹하기 위해 또다른 리스트를 만들었다. 아마 이부분에서 시간 초과가 난게 아닌가 싶다.# 따로 정렬이 필요if can_turn(y2, x2): # 변형 n_pos = sorted([(x1, y1), (y2, x2), (x3, y3)]) n_pos = tuple([*n_pos[0], *n_pos[1], *n_pos[2]]) if n_pos in v: continue v.add(n_pos..