TLE, 시간 초과에 대하여 (BOJ 14500 테트로미노)

첫번째 생각해볼 것 : 이 문제를 브루트포스로 풀 수 있을까?

테트로노미노의 모든 가짓수 (회전을 통해 다르게 보이는 것들 고려)를 다 구해서,

주어진 맵에 대고 움직이며 일일히 합을 다 구해보는 것 (convolution)

→ Q. convolution 함수 구현해볼만 한데? matrix와 kernel 인자로 받아서....

 

 

두번째 :

DFS 4번 돌려서 테트로미노 찾기 가능. 다만, ㅜ 모양의 경우 DFS로는 찾기 불가.

→ Q. len == 2 일때 따로 케이스 설정해주면 가능하려나?

 

ㅜ 모양을 제외한 테트로미노는 DFS로 찾고,

ㅜ 모양은 DFS 이후, ㅜ 모양의 정중앙이 현재 포인트에 오게끔 한 뒤 회전시키며  4 종류의 경우를 다 탐색.

 

DFS는 len 변수를 인자로 주어, len == 4 일시 끝내도록 end condition 설정.

void DFS_four(int x, int y, int sum, int len){
	if (len == 4) {
		sum + world[x][y] // sum under current tetronomino
		return;
	}
    
	...
}

주어진 맵의 모든 포인트가 각각 시작점이 되어 DFS를 돌려야 하고,

DFS는 크기가 4인 도형을 총 28가지 찾으므로, 

$$ O(500^2 * 28 *4) = O(2800만) $$

 

한 포인트에서, 총 28가지의 도형을 찾기 가능. 다른 포인트와의 꼭짓점이 연결되므로, 중복되서 계산되는게 10개씩 발생

 

ㅜ를 찾는 함수 'check_ah'. 현재 포인트를 기준으로 상하좌우 지점의 숫자를 일단 모두 더한 뒤, 하나씩 돌아가며 빼면서 ㅜ 모양의 회전을 구현. 

$$ O(C) $$

// Check ㅜ block with rotations, manually
bool check_wu(int x, int y) {
	int sum = world[x][y];
	vi side;

	// 상하좌우 숫자 더하기 (Boundary 만나면 continue)
	for (int i = 0; i < 4; i++) {
		int x_next = x + direction[i].first;
		int y_next = y + direction[i].second;

		// Boundary check
		if (!(0 <= x_next && x_next < N && 0 <= y_next && y_next < M))
			continue;

		sum += world[x_next][y_next];
		side.push_back(world[x_next][y_next]);
	}

	// Case 1. 사각형 구석 포인트 같은 경우; ㅏ 모양이 만들어지지 않음
	if (side.size() <= 2)
		return false;

	// Case 2. 끝 변에 위치한 포인트; 회전 불가능
	else if (side.size() == 3) {
		each_pt = max(each_pt, sum);
		return true;
	}
	
	// Case 3. 4가지 회전 모두 고려
	for (int i = 0; i < side.size(); i++) {
		each_pt = max(each_pt, sum-side[i]);
	}
	return true;
}

 

Time complexity는 무난함에도 불구하고, 계속 시간 초과가 뜸.

따라서 시도해본 방법들)

1. 불필요한 오버헤드 줄이기

- max 값 구하는데, 벡터에 값을 일일히 저장했다가 맨 마지막에 sort 하고 back() 불러서 꺼내지 말고, 단일 변수를 계속 업데이트 하기;

- 좌표를 pair로 전달하지 말고, int 변수 2개로 나눠서 전달하기

 

2. vector 혹은 pair 같은 container들 함수에 전달할때, parameter에 & (reference)를 붙여서 복사로 전달되지 않도록

3. main 함수의 모든 포인트 loop에서 불필요한 연산들 빼버리기 (성공)

 

수정 전 main loop ( /// 로 제거한 부분 나타냄)

vi max_temp;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
    	///
        each_pt.clear();
        memset(visited, 0, sizeof(visited));
        ///
        
        visited[i][j] = 1;
        DFS_four(make_pair(i, j), 0, 1); // passes 'pair' //

        check_wu({ i,j }); // passes 'pair' //
		
        ///
        auto result = max_element(each_pt.begin(), each_pt.end());
        max_temp.push_back(*result);
        ///
    }
}

수정 후 main loop

memset(visited, 0, sizeof(visited));
each_pt = 0;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {

        visited[i][j] = 1;
        DFS_four(i, j, 0, 1);
        visited[i][j] = 0;

        check_wu(i, j);
    }
}

비교적 작은 연산들이더라도 For-loop이 최대 500 x 500번이나 돌아가므로, 누적될 시 많은 시간이 소요될 수 있다. 

 

간단하지만 의외로 헤맨 시간초과 요인 기록.

 

---

BOJ 14442 - 벽 부수고 이동하기 2

 

반복 연산이 엄청 많이 나타나는 BFS 큐에 custom structure 넣어서 쓰니 TLE, 

tuple로 바꾸니 통과.

 

4. 간단한 데이터 구조 쓰기.