글 읽기 - 퍼즐문제 bfs 백트래킹 반례좀 알려주시면 감사하겠습니다 ㅠ

tpwls1213 6년 전 0

완탐이라 bfs 백트래킹으로하면 모든경우 다해보고 최소를 찾아줄알았는데 23프로정도에서 틀렸습니다가 뜨네요 ㅠㅠ

이문제 아예 접근을 잘못한건가요? 혹시 푸신분 알려주시면 감사하겠습니다 ..!

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int inf = 1e+9;
int map[3][3];
bool check[3][3];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };

int go(int x, int y,int cnt) {
	string str = "";
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			str += (char)map[i][j] + '0';
		}
	}
	if (str == "123456780") return cnt;
	int ret = inf;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (0 <= nx && nx < 3 && 0 <= ny && ny < 3) {
			if (!check[nx][ny]) {
				swap(map[nx][ny], map[x][y]);
				check[nx][ny] = true;
				ret = min(ret, go(nx, ny, cnt + 1));
				swap(map[nx][ny], map[x][y]);
				check[nx][ny] = false;
			}
		}
	}
	return ret;
}
int main() {
	int pos_x, pos_y;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 0) pos_x = i, pos_y = j;
		}
	}
	check[pos_x][pos_y] = true;
	int ans = go(pos_x, pos_y, 0);
	if (ans == inf) puts("-1");
	else printf("%d\n", ans);
	return 0;
}

ehddml3 6년 전 1

31나와야합니다

6 4 7
8 5 0
3 2 1

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

문제

문제

출처

ICPC

퍼즐문제 bfs 백트래킹 반례좀 알려주시면 감사하겠습니다 ㅠ

tpwls1213 6년 전 0

ehddml3 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말