글 읽기 - dfs 함수에서 이동 함수 위치 차이 질문

hanil0623 3년 전 0

g는 이동함수입니다. 주석과 같은 위치에 선언 시 오답을 받고 분기점인 for문 안에서는 정답을 받습니다.

두 함수의 위치 차이가 어떻게 되길래 이런 차이를 보이는건가요? 감사합니다!

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n, ans;
int map[25][25];

void g(int dir) {
	if (dir == 0) {
		for (int j = 1; j <= n; j++) {
			queue<int> q;
			for (int i = 1; i <= n; i++) {
				if (map[i][j] == 0) continue;
				q.push(map[i][j]);
				map[i][j] = 0;
			}
			int cnt = 1;
			while (!q.empty()) {
				int data = q.front();
				q.pop();
				if (map[cnt][j] == 0) {
					map[cnt][j] = data;
				}
				else if (map[cnt][j] == data) {
					map[cnt++][j] *= 2;
				}
				else {
					map[++cnt][j] = data;
				}
			}
		}
	}
	else if (dir == 1) {
		for (int i = 1; i <= n; i++) {
			queue<int> q;
			for (int j = n; j >= 1; j--) {
				if (map[i][j] == 0) continue;
				q.push(map[i][j]);
				map[i][j] = 0;
			}
			int cnt = 1;
			while (!q.empty()) {
				int data = q.front();
				q.pop();
				if (map[i][n+1-cnt] == 0) {
					map[i][n+1-cnt] = data;
				}
				else if (map[i][n+1-cnt] == data) {
					map[i][n+1-cnt++] *= 2;
				}
				else {
					map[i][n+1-++cnt] = data;
				}
			}
		}
	}
	else if (dir == 2) {
		for (int j = 1; j <= n; j++) {
			queue<int> q;
			for (int i = n; i >= 1; i--) {
				if (map[i][j] == 0) continue;
				q.push(map[i][j]);
				map[i][j] = 0;
			}
			int cnt = 1;
			while (!q.empty()) {
				int data = q.front();
				q.pop();
				if (map[n+1-cnt][j] == 0) {
					map[n+1-cnt][j] = data;
				}
				else if (map[n+1-cnt][j] == data) {
					map[n+1-cnt++][j] *= 2;
				}
				else {
					map[n+1-++cnt][j] = data;
				}
			}
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			queue<int> q;
			for (int j = 1; j <= n; j++) {
				if (map[i][j] == 0) continue;
				q.push(map[i][j]);
				map[i][j] = 0;
			}
			int cnt = 1;
			while (!q.empty()) {
				int data = q.front();
				q.pop();
				if (map[i][cnt] == 0) {
					map[i][cnt] = data;
				}
				else if (map[i][cnt] == data) {
					map[i][cnt++] *= 2;
				}
				else {
					map[i][++cnt] = data;
				}
			}
		}
	}
}
void f(int depth, int dir) {
	int score = 0;
	int tmap[25][25];
	memcpy(tmap, map, sizeof(map));
	//g(dir); g는 이동함수입니다. 여기에 선언 시 오답처리를 받고
	
	if (depth == 5) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				score = max(score, map[i][j]);
			}
		}
		ans = max(ans, score);
		return;
	}
	for (int i = 0; i < 4; i++) {
		g(i); // 여기에 선언시 정답처리를 받습니다. 둘의 차이가 무엇인가요..?
		f(depth + 1, i);
		memcpy(map, tmap, sizeof(tmap));
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> map[i][j];
	f(0, 0);
	cout << ans;
	return 0;
}

koreaso2003 3년 전 0

현재 실패한 코드 주석을 풀어서 살펴보면

main => f(0:depth , 0:dir) call => g(0) : 0 방향으로 이=> for 문에서 다시 방향 0부터 -> f( 1: dept, 0 :dir) call -> g(0) 방향으로 이동..

그래서 첫번째 시도에는 이동은 0 방향으로 고정하고 두번째 시도부터 for문을 돌며 4방향을 찾으니 오답이 되는 것 같습니다.

void f(int depth, int dir) {
	int score = 0;
	int tmap[25][25];
	memcpy(tmap, map, sizeof(map));
	g(dir); g는 이동함수입니다. 여기에 선언 시 오답처리를 받고
	
	if (depth == 5) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				score = max(score, map[i][j]);
			}
		}
		ans = max(ans, score);
		return;
	}
	for (int i = 0; i < 4; i++) {
		//g(i); // 여기에 선언시 정답처리를 받습니다. 둘의 차이가 무엇인가요..?
		f(depth + 1, i);
		memcpy(map, tmap, sizeof(tmap));
	}
}

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

문제

문제

출처

ICPC

dfs 함수에서 이동 함수 위치 차이 질문

hanil0623 3년 전 0

koreaso2003 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말