글 읽기 - 과외맨 문제 어떻게 풀어야 되나요? 시간초과. 반례

greeneye 6년 전 0

dfs 로 만든 코드에서 7% 시간 초과가 나옵니다...

bfs 로 만든 코드에서는 7% 에서 틀립니다. 나옵니다
반례 아시는분 계시나요??

/*
1323
스페셜 저지
입력 받고 지나간 길에 대해서 타일 번호를 출력하기.

입력을 받을 때, 
타일번호에 따라서 x1 y1 x2 y2 를 입력받습니다.
맵도 만듭니다.

그리고 타일번호가 같다면, 그쪽으로 이동하고, 리턴하면 됩니다. 오께이.

*/


#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

#define SIZE 5 // 501
int map[SIZE][SIZE * 2];
int visit[SIZE][SIZE * 2];
int x, y, nx, ny;
int dx[] = { 0,1,-1,0 }; // 오른쪽, 아래, 위, 왼
int dy[] = { 1,0,0,-1 };
int maxTileNum, curTileNum;
int use_store[SIZE*SIZE - SIZE / 2 + 1];
int N;
int use_tile[SIZE*SIZE - SIZE/2+1];
int ans;
int tileNum, ntileNum;
int flag;

/*
i가 홀수이면 첫번째 [i][0] = 0;
*/
void problemIn() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		if (i % 2 == 1) {
			map[i][0] = 0;
			map[i][N * 2] = 0;
			{
				for (int j = 1; j < (N * 2) - 1; j++) {
					cin >> map[i][j];
				}
			}
		}
		else {
			for (int j = 0; j < N * 2; j++) {
				cin >> map[i][j];
			}
		}
	}
}
/*
마지막 줄의 마지막 타일로 이동할 수 없는 경우. 이 경우에는 번호가 가장 큰 타일로
이동하면 됩니다. 

4회전 해서 갈 곳이 없는 경우,
지금까지의 사용한 타일의 갯수와 경로를 출력해주면 됩니다. 
만들어보겠습니다. 반례를
*/
void copy_arr(int a[SIZE*SIZE - SIZE / 2 + 1], int b[SIZE*SIZE - SIZE / 2 + 1]) {
	for (int i = 1; i < N*N - (N / 2) + 1; i++)
		b[i] = a[i];
}


void dfs(int depth, int x, int y) {

	if (flag == 1) return;

	if (x == N - 1 && y == 2 * N - 1) {
		// ans 의 갯수 세기
		for (int i = 1; i < N*N - (N / 2)+1; i++) {
			if (use_tile[i] == 1) {
				ans++;
			}
		}
		cout << ans << endl;
		// 배열의 값 출력
		for (int i = 1; i < N*N - (N / 2)+1; i++) {
			if (use_tile[i] == 1) {
				cout << i << " ";
			}
		}
		flag = 1;
		return;
	}


	int turnCnt = 0;
	
	for (int i = 0; i < 4; i++) {
		turnCnt++;
		tileNum = ((x % 2 == 0) ? (x*N + y / 2) : (x*N + (y - 1) / 2)) + 1 - ((x > 0) ? (x / 2) : 0);
		use_tile[tileNum] = 1;
		visit[x][y] = 1;

		nx = x + dx[i];
		ny = y + dy[i];
		if (nx >= 0 && ny >= 0 && nx < N && ny < N*2 && visit[nx][ny] == 0) { // map 안에 들어오고,
			ntileNum = ((nx % 2 == 0) ? (nx*N + ny / 2) : (nx*N + (ny - 1) / 2)) + 1 - ((x > 0) ? (x / 2) : 0);
			if (map[nx][ny] == map[x][y] || tileNum == ntileNum) {
				dfs(depth+1, nx, ny);
			}
		}

		// 사방이 막혀 있는 경우, 
		/*
			1. 최고타일넘버를 비교합니다. 먼저 현재의 최고타일 넘버는 몇인지? 찾고,
			2. 기존의 타일 넘버와 비교해서 큰 것을 복사합니다.
		*/
		if (turnCnt == 4) {
			for (int i = 1; i < N*N - (N / 2) + 1; i++) {
				if (use_tile[i] == 1) {
					curTileNum = max(curTileNum, i);
				}
			}

			if (curTileNum > maxTileNum) {
				maxTileNum = curTileNum;
				copy_arr(use_tile, use_store);
			}
		}
	}
	use_tile[tileNum] = 0;
	visit[x][y] = 0;
}


void solve() {

	dfs(0, 0, 0);
	if (flag == 0) {
		for (int i = 1; i < N*N - (N / 2) + 1; i++) {
			if (use_store[i] == 1) {
				ans++;
			}
		}
		cout << ans << endl;
		// 배열의 값 출력
		for (int i = 1; i < N*N - (N / 2) + 1; i++) {
			if (use_store[i] == 1) {
				cout << i << " ";
			}
		}
	}
}

int main() {
	ans = 0;
	problemIn();
	solve();

	return 0;
}

jh05013 6년 전 1

적당히 큰 입력을 아무거나 만들어서 넣으면 런타임 에러가 납니다. DFS로 최단거리를 찾으면 안 됩니다.

greeneye 6년 전 0

BFS로 갈 수 있는 곳 까지 찾고, 그 길까지를 다시 DFS로 찾아서 풀이했는데도 7%에서 틀립니다가 나오네요.
힌트좀 주세요 ㅠㅠ
출처 찾아가서 테스트케이스 3개에 대해서는 맞게 수정 했습니다.

/*
dfs말고 큐로 풀어보도록 하겠습니다.
*/

#include <iostream>
#include <queue>
#include <algorithm>
#include <stack>

using namespace std;

#define SIZE 501 // 501
int map[SIZE][SIZE * 2];
int visit[SIZE][SIZE * 2];
int visit_dfs[SIZE][SIZE * 2];
int use_tile[SIZE*SIZE - SIZE / 2 + 1];
int use_tile_dfs[SIZE*SIZE - SIZE / 2 + 1];
int printArr[SIZE*SIZE - SIZE / 2 + 1];
int test_Arr[SIZE*SIZE - SIZE / 2 + 1];
int x, y, nx, ny;
int dx[] = { 0,1,-1,0 };  //
int dy[] = { 1,0,0,-1 };
int maxTileNum, curTileNum;
int N;
int flag;
int ans;
int tileNum, ntileNum;
int index;
int f_x, f_y;
struct points {
	int x, y;
};
queue<points> que;
stack<int> test;

/*

*/
void problemIn() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		if (i % 2 == 1) {
			map[i][0] = 0;
			map[i][N * 2] = 0;
			{
				for (int j = 1; j < (N * 2) - 1; j++) {
					cin >> map[i][j];
				}
			}
		}
		else {
			for (int j = 0; j < N * 2; j++) {
				cin >> map[i][j];
			}
		}
	}
}

/*
갈 수 있는 만큼 가고, 간곳들의 타일들은 어떻게 계산할 수 있지?
만약에 bfs 로 갈 수 있는 곳을 모두 탐색한다음에, 4,9 가 1로 표시되어 있으면, 그곳을 가기 위해 필요한 타일들을 세고,
그 타일들의 숫자를 파악합니다. 

현재 주어진 비지트 맵으로 다시 0으로 찾아가는 길을 찾을 수 있는지?
여기서 필요한 길만 어떻게 찾을 수 있나요?

*/

void bfs() {
	
	while (!que.empty()) {
		x = que.front().x;
		y = que.front().y;
		que.pop();
		tileNum = ((x % 2 == 0) ? (x*N + y / 2) : (x*N + (y - 1) / 2)) + 1 - ((x > 0) ? (x / 2) : 0);
		for (int i = 0; i < 4; i++) {
			nx = x + dx[i];
			ny = y + dy[i];
			ntileNum = ((nx % 2 == 0) ? (nx*N + ny / 2) : (nx*N + (ny - 1) / 2)) + 1 - ((x > 0) ? (x / 2) : 0);
			if (nx >= 0 && ny >= 0 && nx < N && ny < N * 2 && visit[nx][ny] == 0 && map[nx][ny] != 0) {
				if (map[nx][ny] == map[x][y] || tileNum == ntileNum) {
					visit[nx][ny] = 1;
					use_tile[tileNum] = 1;
					que.push({ nx,ny });
				}
			}
		}
	}
}

void print_fuc() {

	//for (int i = 1; i < N*N - (N / 2) + 1; i++) {
	//	if (use_tile_dfs[i] == 1) {
	//		ans++;
	//	}
	//}
	//cout << ans << endl;
	//// 배열의 값 출력
	//for (int i = 1; i < N*N - (N / 2) + 1; i++) {
	//	if (use_tile_dfs[i] == 1) {
	//		cout << i << " ";
	//	}
	//}

	int length = test.size();
	for (int i = 0; i < length; i++) {
		printArr[length - 1 - i] = test.top();
		test.pop();
	}

	cout << length << endl;
	for (int i = 0; i < length; i++) {
		cout << printArr[i] << " ";
	}

	flag = 1;
	return;
}

void dfs(int x, int y) {

	if (flag == 1) return;

	for (int i = 0; i < 4; i++) {
		tileNum = ((x % 2 == 0) ? (x*N + y / 2) : (x*N + (y - 1) / 2)) + 1 - ((x > 0) ? (x / 2) : 0);
		use_tile_dfs[tileNum] = 1;
		if (!test.empty()) {
			if (test.top() != tileNum) {
				test.push(tileNum);
			}
		}
		visit_dfs[x][y] = 1;

		if (x == f_x && y == f_y) {
			print_fuc();
			return;
		}

		nx = x + dx[i];
		ny = y + dy[i];
		if (nx >= 0 && ny >= 0 && nx < N && ny < N * 2 && visit_dfs[nx][ny] == 0) { // map 안에 들어오고,
			ntileNum = ((nx % 2 == 0) ? (nx*N + ny / 2) : (nx*N + (ny - 1) / 2)) + 1 - ((x > 0) ? (x / 2) : 0);
			if (map[nx][ny] == map[x][y] || tileNum == ntileNum) {
				dfs(nx, ny);
			}
		}
	}
	use_tile_dfs[tileNum] = 0;
	if (!test.empty()) {
		test.pop();
	}
	visit_dfs[x][y] = 0;
}

void solve() {

	que.push({ 0,0 });
	visit[0][0] = 1;
	use_tile[1] = 1;
	bfs();

	for (int i = N - 1; i >= 0; i--) {
		for (int j = (N * 2) - 1; j >= 0; j--) {
			if (visit[i][j] == 1) {
				f_x = i;
				f_y = j;
				test.push(1);
				dfs(0, 0);
			}
			if (flag == 1) break;
		}
		if (flag == 1) break;
	}
}

int main() {
	problemIn();
	solve();

	cout << " "<< endl;
	return 0;
}

jh05013 6년 전 1

코드를 자세히 읽지 않았지만, DFS로 최단경로를 찾으면 최단경로가 아니거나 (즉 돌아서 가는 길을 DFS 했거나), 지수 시간이 걸립니다. 경로 복원도 가장 큰 타일을 구하면서 같이 구해야 합니다.

dongwook 5년 전 1

7%에서 틀리시면 아마 '마지막 타일에 도달하지 못 했을 때' 테스트 케이스에 실패하신 겁니다. 저는 타일번호와 조각번호를 구분하지 않아서 틀렸습니다. 타일번호는 타일의 인덱스 번호이고 조각 번호는 타일을 이루는 두 개의 조각에 적힌 번호입니다.

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

문제

문제

출처

ICPC

과외맨 문제 어떻게 풀어야 되나요? 시간초과. 반례

greeneye 6년 전 0

jh05013 6년 전 1

greeneye 6년 전 0

jh05013 6년 전 1

dongwook 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말