글 읽기 - 3x3 퍼즐문제 양방향 탐색으로 풀려면 어떻게 해야되나요?

akane 6년 전 0

단방향 bfs로 정답 받고 양방향 도전하려는데 메모리초과만 뜨네요...

제 생각엔 경로가 없는 경우에서 O( 2 x 단방향 bfs ) 시간&메모리가 걸려 그런 것 같은데

양방향으로는 못 푸는 문제인건가요?

#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;

const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};
//절대값 1증가
int incr(int n){if(n<0) return n-1; return n+1;}
//부호 비교
bool sgn(int a){if(a<0) return 1; return 0;}

int bfs(int start, int finish){
	int here, there, cn, nn, cx, cy, nx, ny, arr[3][3];
    
	map<int, int> disc;
	queue<int> q;
	if(start == finish) return 0;
	q.push(start); disc[start] = 1;
    //도착점에서 시작하는 bfs, 음수인 것으로 방향을 정하고 절대값은 최단거리
	q.push(finish); disc[finish] = -1;
	
    while(!q.empty()){
		here = q.front(); q.pop();
		cn = disc[here];
		for(int i =2; i>=0; --i) for(int j =2; j>=0; --j){
			if(here%10 == 0) cy = i, cx = j;
			arr[i][j] = here%10, here/=10;
		}
		for(int w=0; w<4; ++w){
			there =0;
			ny= cy+dy[w], nx= cx+dx[w];
			if(ny<0||nx<0||ny==3||nx==3) continue;
			swap(arr[cy][cx], arr[ny][nx]);
			for(int i =0; i<3; ++i) for(int j =0; j<3; ++j)
				there = there*10 + arr[i][j];
			nn = disc[there];
            //there을 방문한 적이 없다면 queue에 추가
			if(!nn){
				disc[there] = incr(cn);
				q.push(there);
			}
            //there을 방문했고 현재 탐색하는 방향과 다르다면 (= 부호가 다르다면)
			else if(sgn(nn) != sgn(cn))
                //절대값을 더하고 겹치는 노드가 한개이므로 -1 하여 return
				return abs(nn) + abs(cn) -1;
			swap(arr[cy][cx], arr[ny][nx]);
		}
	}
    //
	return -1;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int x, start = 0, finish = 123456780;
	for(int i =0; i<3; ++i) for(int j =0; j<3; ++j)
		cin >> x, start = start*10 + x;
	cout << bfs(start, finish);
}

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

문제

문제

출처

ICPC

3x3 퍼즐문제 양방향 탐색으로 풀려면 어떻게 해야되나요?

akane 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말