clrmt   2달 전

틀린 이유는 제가 항상 큐 대신 원형 큐를 사용하고 있고,

이 코드에서는 원형 큐 크기가 2048로 되어 있습니다.

즉,

q[qFront++] = ...

qFront &= 2048 - 1

...

q[qBack++] = ...

qBack &= 2048 - 1

로 되어 있습니다.

원형 큐 크기가 2048이 되면 아래와 같은 케이스에서 문제가 일어나는데

preview

위와 같은 케이스에서 왼쪽 위에서 출발해 녹색 길을 따라 BFS로 퍼트려질 경우 최악의 경우에 빨간색 선에 위치하는 노드의 개수만큼의 큐 안에 동시에 들어가 있어야 하므로 약 3000개 + (직전의 노드 일부) 정도의 크기가 필요한게 아닐까 합니다.

문제는, 1000x1000에서 BFS를 돌렸을 때 원형 큐에 필요한 크기가 가장 커지도록 케이스를 만들고 싶은데 지역해정도는 위에 나온 것처럼 직접 채워나가면 지만 전역해는 어떻게 구할지 모르겠어서 글을 남겨봅니다. 다른 좋은 방법이 있을까요?

sait2000   2달 전

preview

전역적으로 최대인지는 잘 모르겠지만 이렇게 하면 좀 더 길 거 같습니다.

sait2000   2달 전

생각해보니까 시작점을 막을 필요 없이 벽을 두께 2짜리로 하면 부순 거랑 안 부순 거 해서 큐 길이가 두 배가 될 거 같네요

sait2000   2달 전

일단 큐 사이즈가 9240쯤까지 가는 데이터입니다

sait2000   2달 전

생각해보니까 3개로 자르지 말고 4개로 자르면 더 빽빽히 채울 수도 있겠네요

preview

clrmt   2달 전

아 저렇게 하니까 깔끔하게 채워지네요.

만들어주신 케이스가 답은 1999인데 23712110 코드는 -1이 나오고 큐의 크기 8192까지 올려도 오답이 나옵니다.

처음 생각했을 땐 가운데의 점 하나로부터 퍼트려지는 케이스를 생각해 2000이라고 생각했었는데... 그 4배를 넘네요

구조를 바꿔서 더 나은 해를 찾을 수도 있을 것 같기도 하지만 일단 이대로 요청을 올려보겠습니다.

clrmt   2달 전

앗... 혹시 가운데까지는 일단 간 다음에 거기서부터 분기해서 맵을 꽉 채울 수도 있을까요?

clrmt   2달 전

preview

대충 이렇게 하면 되나

clrmt   2달 전

엌ㅋㅋ 한계까지 끌어모으기

preview

sait2000   2달 전

저렇게 가운데에서 4개로 나눠지면 각각 나눠진 걸 또 원래 문제처럼 생각해서 더 잘게 나누면 많이 커질 것 같긴 하네요

clrmt   2달 전

preview

어찌저찌 여기까진 했습니다.

clrmt   2달 전

preview

생각해보니까 이렇게 계속 쪼개면 더 늘어날 것 같기도 하네요. 생각했던 것보다도 훨씬 더 커질 것 같기도...?

clrmt   2달 전

테케 만들기가... 복잡하네요. 나중에 시간나면 해야할 듯 합니다. 제가 푼 BFS들은 이제 망한걸로 결론을 내리고...

도움 주셔서 감사합니다.

댓글을 작성하려면 로그인해야 합니다.