글 읽기 - dfs 구현시 효율적인 방법이 궁금합니다.

cjy0619 5년 전 1

다음은 제 dfs함수구현부분입니다. moveBoard 와 fusion 함수를 통해 해당 방향으로 옮기게 됩니다.

이때 board는 현재 전역변수로 선언 되어 있기에, 값이 계속 변하는 상황입니다.

이 문제가 아니더라도 dfs 구현시 방문노드를 확인할 때 어떻게 처리할지 항상 헤매고 있습니다.

아래 코드의 경우 현재 상태를 새로 배열을 만들어서 저장 뒤, 한스택이 끝난 뒤 복구 시켜주는 방법으로 구현했습니다.

매번 탐색때마다 새로 배열을 통해 저장하기에 너무 비효율적인것 같아요, 좀 더 나은 방법 있을 까요?

void dfs( int count) {

int temp[22][22];
for (int i = 0; i < 22; i++) {
for (int j = 0; j < 22; j++) {
temp[i][j] = board[i][j];
}
}
if (count == 5) {
return;
}

moveBoard(1); // 오른쪽
fusion(1);
moveBoard(1);
dfs(count + 1);

for (int i = 0; i < 22; i++) {
for (int j = 0; j < 22; j++) {
board[i][j] = temp[i][j];
}
}

moveBoard(2); //왼쪽
fusion(2);
moveBoard(2);
dfs(count + 1);

for (int i = 0; i < 22; i++) {
for (int j = 0; j < 22; j++) {
board[i][j] = temp[i][j];
}
}

moveBoard(3); //위
fusion(3);
moveBoard(3);
dfs(count + 1);

for (int i = 0; i < 22; i++) {
for (int j = 0; j < 22; j++) {
board[i][j] = temp[i][j];
}
}

moveBoard(4); //아래
fusion(4);
moveBoard(4);
dfs(count + 1);

for (int i = 0; i < 22; i++) {
for (int j = 0; j < 22; j++) {
board[i][j] = temp[i][j];
}
}
}

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

문제

문제

출처

ICPC

dfs 구현시 효율적인 방법이 궁금합니다.

cjy0619 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말