이번에도 D2 문제를 풀어본다!
생각한 풀이 방식은 다음과 같다
맨 윗줄 ➡️ 맨 오른쪽 줄 ⬇️ 맨 아랫줄 ⬅️ 맨 왼쪽 줄 ⬆️으로 숫자를 하나씩 증가시키며 채워 나가되, 사각형의 크기를 점점 줄여주는 것이다.
열심히 그렸는데 하나도 안와닿는 그림이군. 삐뚤빼뚤
아무튼,
start = 0, end = N-1로 설정하고, for문 네 개로 가장 바깥쪽 테두리의 숫자를 채운 후,
start++, end--로 범위를 좁혀가며 end가 start보다 작아질 때까지 반복한다.
시간 복잡도는 O(T*N^2)로, 1 ≤ N ≤ 10라서 충분하다!
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(int argc, char** argv)
{
int test_case;
int T, N, i, j, start, end, num;
cin>>T;
vector <vector <int>> snail;
for(test_case = 1; test_case <= T; ++test_case)
{
cin>>N;
snail.clear();
snail.resize(N,vector<int>(N,0));
start=0;
end=N-1;
num=1;
while(start<end){
for( i=start; i<=end; i++ ){
snail[start][i]=num++;
}
for( i=start+1;i<=end;i++){
snail[i][end]=num++;
}
for( i=end-1;i>=start;i--){
snail[end][i]=num++;
}
for( i=end-1;i>start;i--){
snail[i][start]=num++;
}
start++;
end--;
}
if(start==end) snail[start][start]=num++;
cout<<"#"<<test_case<<"\n";
for( i=0;i<N;i++){
for( j=0;j<N;j++){
cout<<snail[i][j]<<" ";
}
cout<<"\n";
}
}
return 0;
}
snail.clear();를 사용하지 않으면 두 번째 테스트케이스부터 이상한 결과가 나왔다.찾아보니,
C++에서resize()는 벡터의 크기를 변경하지만, 메모리 용량(capacity)은 그대로 유지할 수 있다고 한다. 즉, 벡터가 이전 테스트케이스에서 할당한 메모리를 그대로 사용하면서 이전 데이터가 남아 있을 수 있다는 의미다.크기를 바꾸고 0으로 초기화까지 했는데 왜 그런지 정확히는 모르겠지만..
벡터를 재사용할 때clear()는 꼭 해 줘야겠다
다른 풀이를 찾아보니, 방향 d를 설정해 계속 바꿔가며 진행하는 방식과 DFS를 활용한 풀이도 있었다. 내 방법도 좋지만, DFS를 적용할 생각은 전혀 못했다....! 다양하게 생각해보기:)
