테스트 준비 중인데... 시험 시에 조건이 stdio.h 이외의 라이브러리를 사용할 수 없게 되어 있어서요(ㅠㅠ) 연습 삼아 직접 구현해 보는 중이에요.

혹시 큐 구현에 문제가 있는건가요?

큰 문제 몇 가지만 말씀드리자면,

1. freopen 지워야 합니다.
2. 큐의 크기가 2000으로는 절대 충분하지 않습니다. 최악의 경우 1000*1000 = 1000000칸을 모두 큐에 넣게 될 수 있습니다.
3. 67, 73번째 줄에서는 -1번째 인덱스에 접근할 위험성이 있고, 이 인덱스의 위치에 무슨 값이 들어있을지는 알 수 없습니다.
4. 실행은 되지만 권장되지 않는 문장이 많이 보입니다. 대표적으로 4번째 줄에 Box가 타입이 없이 선언된 것, pop의 인자에도 타입이 없는 것, void 함수인 push에서 return 0으로 값을 반환하고 있는 것 등이 있습니다.

1. 큐 최대 사이즈가 너무 작습니다.
2. Q_n과 Q_m의 정의를 분명히 해주세요. 이는 배열의 인덱스를 저장하는 변수인가요? 아니면 배열의 원소를 저장하는 변수인가요?
3. main의 freopen은 지워주세요.
4. 소스가 너무 불친절합니다. 주석이라도 달아주셨으면 좋겠습니다

대회에서 어떻게 했는지는 중요하지 않습니다. 그런 형식의 입출력 문제를 BOJ에서 지원하지 않기 때문에 모든 문제는 전부 stdin에서 입력을 받아서 stdout에 출력해야 합니다.

@dmj03718 , @lolicon 님, 친절한 답변 감사 드립니다.

지적해 주신 사항들을 기반으로 아래와 같이 모두 수정해 보았습니다만, 여전히 반례를 찾지 못하고 있습니다..  뭐가 잘못된건지 모르겠네요...ㅠㅠ

(분명 로컬에선 모든 반례와 기본입력이 정답으로 나오는데두요..ㅠㅠ)

1. freopen 은 제가 로컬에서 짜던 코드를 질문란에 옮기면서 삭제를 하지 않은 행이었습니다 ^^; 
2. 큐 사이즈를 1000 x 1000 으로 하여 아래에 다시 구현 했습니다.
3. Q_n, Q_m 은 글로벌 변수로 선언을 해 두어 Queue 값의 원소를 가져오기 위한 변수로 만든 것입니다.
4. 67, 73 번 줄은 Box[n-1] >= 0 이 아니라 n-1값이  0보다 큰 경우이기 때문에, 지적해 주신것 처럼 -1 번째 인덱스에는 접근 하지 않을 것 같아요.
5. Box 타입선언과 pop 인자 타입 선언, void 함수의 리턴값 등을 모두 수정하였습니다.
6. 소스의 각 부분에 주석을 달아 보았습니다.

(참고로, Queue 함수는 n과 m 을 한칸씩 써서 두칸을 한묶음으로 하여 직접 구현했습니다.)

보니까 Queue 배열에 한 번에 2개씩의 값 (행, 열)을 동시에 넣고 빼고 있는데, 이러면 1000000개의 원소로는 최대 50만 칸밖에 표현하지 못합니다.

배열 인덱스 관련된 부분은 뒤쪽 조건을 놓치기는 했는데, 그래도 여전히 안전하지는 않은 코드입니다. 예를 들어 n이 0인 상황에서 66번째 줄에 도달하면 무조건 Box[-1][m]을 보게 되는데, 이 부분은 배열의 할당 범위를 벗어난 곳이므로 곧바로 런타임 에러가 나도 이상하지 않습니다. 뒤에 n - 1 >= 0 이라는 조건이 있지만 이는 먼저 && 앞의 문장을 실행해서 그 결과가 참이면 실행하는 문장이므로, 여기가 실행되기 전에 먼저 잘못된 배열 인덱스에 접근할 경우 문제가 생길 수 있습니다. 순서를 바꿔줘야 합니다.

@djm03718 님 답변 감사 드립니다.

조언 해 주신대로 조건문의 순서를 바꾸어서 다시 돌려 봤습니다만, 이번에는 시간초과가 나오네요. 

3중 for문이 있는 것도 아니구 구현이 제 생각으로는 꽤 단순해 보이긴 하는데 어딘가 잘못된 부분이 있을까요. 

Queue 배열을 2000000 으로 했을때는 런타임 에러가 나옵니다.. 

3중 for문은 아니지만 그에 준하는 작업이 있습니다. pop 함수를 보시면 20번째 줄에서 뒤의 원소를 전부 2칸씩 앞으로 당겨오고 있는데, 큐에 최대 O(N*M)개의 원소가 들어가있고 pop 역시 O(N*M)번을 해야 하므로 총 O((NM)^2)의 시간복잡도가 됩니다.

또 잘못된 곳이, 63, 69번째 줄에서 <= N, <= M으로 하고 있지만 실제로 유효한 좌표는 N-1, M-1까지이므로 < N, < M으로 쓰는 것이 맞습니다. 물론 또한 이들도 범위 검사를 먼저 해야 합니다.

큐에서 pop의 시간을 개선하려면 뒤의 원소를 당겨오지 말고, 큐의 맨 첫 부분이 어디인지를 가리키는 변수를 만들고 그 변수를 증가시키는 것으로 대체하면 됩니다.

여기까지 고치니 맞았습니다.

위에서 방금 말씀드린 것 하나를 안 고치셨습니다.

"또 잘못된 곳이, 63, 69번째 줄에서 <= N, <= M으로 하고 있지만 실제로 유효한 좌표는 N-1, M-1까지이므로 < N, < M으로 쓰는 것이 맞습니다. 물론 또한 이들도 범위 검사를 먼저 해야 합니다."

@djm03178 님 답변 감사 드립니다.  분명히 위의 pop 구현으로는 매번 pop 함수를 호출할 때마다 전체 Queue 값을 재배열 해야 하는 복잡도가 생기네요.. 

아래와 같이  rear / front 플래그를 써서  deque() 함수로 다시 구현 해 보았습니다. 하지만 이번에도 역시 시간 초과가 나오네요.. 대체 어디서 시간을 먹는지 모르겠습니다.

큐의 크기가 왜 다시 100만으로 줄어들었나요?

@djm03178 헉.... 처음 Queue 선언 시에 배열 값을 잘못 넣었었네요 ^^ 수정하고 돌려보니 정답이 나왔습니다!!!! 

int Queue[2000000] = { 0, };

휴... 갈길이 정말 머네요. 덕분에 많은 공부가 되었습니다. 감사합니다!