글 읽기 - 어디서 시간초과가 나는지 모르겠습니다.

dudwls901 2년 전 1

그래프를 이동시키는 부분이 문제인가요??

이동시키는 로직 말고는 의심스러운 부분이 없어서 계속 고쳐봤는데 계속 시간초과가 뜨네요

#include <iostream>
#include <algorithm>
#include <vector>

#define MAX 20
using namespace std;

int n;
//1<= n<=20
int answer;

vector<vector<int>> moveGraph(int direct, vector<vector<int>>graph) {
	vector<vector<int>> graphCopy(n, vector<int>(n, 0));
	//return graphCopy;
	//우
	if (direct == 0) {
		for (int r = 0; r < n; r++) {
			int inIdx = n - 1;
			for (int c = n - 1; c >= 0; c--) {
				if (graph[r][c] == 0) continue;
				int next = c - 1;
				bool isIn = false;
				while (next >= 0) {
					if (graph[r][next] == 0)continue;
				
					if (graph[r][next] == graph[r][c]) {
						graphCopy[r][inIdx--] = graph[r][c] * 2;
						c=next;
						isIn = true;
						break;
					}
					else {
						graphCopy[r][inIdx--] = graph[r][c];
						graphCopy[r][inIdx--] = graph[r][next];
						c=next-1;
						isIn = true;
						break;
					}
				}
				if (!isIn) {
					graphCopy[r][inIdx] = graph[r][c];
				}
			}
		}
	}
	//하
	else if (direct == 1) {
		for (int c = 0; c < n; c++) {
			int inIdx = n - 1;
			for (int r = n - 1; r >= 0; r--) {
				if (graph[r][c] == 0) continue;
				int next = r - 1;
				bool isIn = false;
				while (next >= 0) {
					if (graph[next][c] == 0)continue;

					if (graph[next][c] == graph[r][c]) {
						graphCopy[inIdx--][c] = graph[r][c] * 2;
						r =next;
						isIn = true;
						break;
					}
					else {
						graphCopy[inIdx--][c] = graph[r][c];
						graphCopy[inIdx--][c] = graph[next][c];
						r=next-1;
						isIn = true;
						break;
					}

				}
				if (!isIn) {
					graphCopy[inIdx][c] = graph[r][c];
				}
			}
		}
	}
	//좌
	else if (direct == 2) {
		for (int r = 0; r < n; r++) {
			int inIdx = 0;
			for (int c = 0; c < n; c++) {
				if (graph[r][c] == 0) continue;
				int next = c+1;
				bool isIn = false;
				while (next < n) {
					if (graph[r][next] == 0)continue;
					if (graph[r][next] == graph[r][c]) {
						graphCopy[r][inIdx++] = graph[r][c] * 2;
						c=next;
						isIn = true;
						break;
					}
					else {
						graphCopy[r][inIdx++] = graph[r][c];
						graphCopy[r][inIdx++] = graph[r][next];
						c=next+1;
						isIn = true;
						break;
					}
				}
				if (!isIn) {
					graphCopy[r][inIdx] = graph[r][c];
				}
			}
		}
	}
	//상
	else {
		for (int c = 0; c < n; c++) {
			int inIdx = 0;
			for (int r = 0; r <n; r++) {
				if (graph[r][c] == 0) continue;
				int next = r + 1;
				bool isIn = false;
				while (next < n) {
					if (graph[next][c] == 0)continue;

					if (graph[next][c] == graph[r][c]) {
						graphCopy[inIdx++][c] = graph[r][c] * 2;
						r=next;
						isIn = true;
						break;
					}
					else {
						graphCopy[inIdx++][c] = graph[r][c];
						graphCopy[inIdx++][c] = graph[next][c];
						r=next+1;
						isIn = true;
						break;
					}

				}
				if (!isIn) {
					graphCopy[inIdx][c] = graph[r][c];
				}
			}
		}
	}

	return graphCopy;
}

void dfs(int depth, vector<vector<int>> graph) {
	if (depth == 5) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				answer = max(answer, graph[i][j]);
			}
		}
		return;
	} 

	for (int i = 0; i < 4; i++) {
		dfs(depth + 1, moveGraph(i, graph));
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	vector<vector<int>> graph(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j];
			answer = max(graph[i][j], answer);
		}
	}
	dfs(0, graph);
	cout << answer;

	return 0;
}

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

문제

문제

출처

ICPC

어디서 시간초과가 나는지 모르겠습니다.

dudwls901 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말