글 읽기 - dfs로는 안되나요?

jsh 7년 전 0

다른방법인 map을 써서 풀긴 풀었는데..

아래의 소스(dfs)로 시간초과는 발생하지는 않고 틀렸습니다만 나타납니다.

아래의 알고리즘으로도 해결될 수 있을 것 같은데...

반례나 틀리는이유를 알고싶습니다

#include <iostream>

using namespace std;

int ans[3][3] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 0 } };
int g[3][3], zi, zj;
int chk[3][3], minStep = 98765432;
int dir[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

void sol(int r, int c, int step) {
	if (r == 2 && c == 2)  {
		bool flag = true;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (ans[i][j] != g[i][j]) {
					flag = false;
					break;
				}
			}
			if (!flag) break;
		}
		if (flag && (minStep > step)) {
			minStep = step;
		}
	}
	chk[r][c] = step;

	for (int i = 0; i < 4; i++) {
		int nR = r + dir[i][0];
		int nC = c + dir[i][1];
		
		if (nR < 0 || nC < 0 || nR >= 3 || nC >= 3)
			continue;
		if (chk[nR][nC] != -1 && chk[nR][nC] <= step + 1)
			continue;

		g[r][c] = g[nR][nC];
		g[nR][nC] = 0;
		sol(nR, nC, step + 1);
		g[nR][nC] = g[r][c];
		g[r][c] = 0;
	}

	chk[r][c] = -1;
}
int main() {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> g[i][j];
			if (g[i][j] == 0) {
				zi = i;
				zj = j;
			}
			chk[i][j] = -1; 
		}
	}

	sol(zi, zj, 0);
	
	if (minStep == 98765432) {
		cout << -1 << '\n';
	}
	else {
		cout << minStep << '\n';
	}
	
	return 0;
}

hoyun293 5년 전 0

와 이분 저랑 거의 비슷하게 하셨네 dfs..

저도 틀렸습니다 나왔습니다.

6 4 7

8 5 0

3 2 1

도 나오시나요 ? 답이 31인가 32이였습니다.

저는 여기서 -1나오네요

hoyun293 5년 전 1

jsh 님도 -1나오네요 흠 제 생각에는 저희 방식대로 돌리면 계속 못돌아요 백트래킹하면 하면 최대 깊이8? 밖에 못들어가는거 같네요

답이 31인거 보니까 저희처럼 하면 안되는듯

hacastle 2년 전 1

감사합니다.

if (chk[nR][nC] != -1 && chk[nR][nC] <= step + 1)를 이용해서 visit 역할을 할 수 있었네요. 전 다른 방법(2진법)으로 하니 step저장에서 문제가 있었는데..

좋은 방법 배워갑니다.

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

문제

문제

출처

ICPC

dfs로는 안되나요?

jsh 7년 전 0

hoyun293 5년 전 0

hoyun293 5년 전 1

hacastle 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말