[성실코딩 21일차] SWEA #2819 격자판의 숫자 이어 붙이기 *

DFS로 모든 경우의 수 다 확인하는 방법으로 풀었는데

시간 초과 나왔다.

 

문제풀이를 DP로 수정해보려했는데 모르겠어서 다른 사람코드 보는데

똑같은 DFS방법인데 시간초과가 안난다!!!!!

 

• 시간 단축할 수 있는 방법

1. 이미 생성된 적 있는 숫자인지 확인(중복숫자 확인) -> 함수사용하지않고, 생성가능한 숫자 크기만큼 배열할당해서 1로 표시

2. 일곱자리숫자 만들기 -> 함수사용하지않고, dfs재귀로 부를때마다 숫자를 바로바로 생성해줌. *10

 

test case마다 재사용하는 변수는 초기화잊지말기!

#include <iostream>
#include <string>
#include <vector>
#include <cstring>

using namespace std;

int dr[4] = { 0,0,1,-1 }; // 동서남북
int dc[4] = { 1,-1,0,0 };

int map[4][4];
char checkNum[10000000] = { 0, }; // 최대 숫자: 9999999

void putNum(int _r, int _c, int _number, int _idx) {
	if (_idx==7) { // 마지막 인덱스까지 끝냄
		// 만들어진 숫자 체크
		checkNum[_number] = 1;
		return;
	}
	_number *= 10;
	_number += map[_r][_c];

	for (int k = 0; k < 4; k++) { // 동서남북 4방향
		
		int new_r = _r + dr[k];
		int new_c = _c + dc[k];
		
		if ((new_r<0 || new_r>3)||
			(new_c<0 || new_c>3)) { // boundary check
			continue;
		}
		else {
			putNum(new_r,new_c,_number,_idx+1);
		}
	}
}

int main() {

	int tc;
	cin >> tc;
	for (int i = 1; i <= tc; i++) {
		int result=0;
		//초기화
		memset(checkNum,0,sizeof(char)*10000000);
		// 입력
		for (int r = 0; r < 4; r++) {
			for (int c = 0; c < 4; c++) {
				cin >> map[r][c];
			}
		}
		//연산
		for (int r = 0; r < 4; r++) {
			for (int c = 0; c < 4; c++) {
				putNum(r,c,0,0);
			}
		}
		// 만들어진 숫자 갯수 확인
		for (int k = 0; k < 10000000; k++) {
			if (checkNum[k]==1) {
				result++;
			}
		}

		// 출력
		cout << "#" << i << " " << result << endl;
	}
	return 0;
}