글 읽기 - 알고리즘 질문 드립니다.

poia0304 6년 전 0

제가 생각한 알고리즘은 다음과 같습니다.

좌표 i,j 위치에서 상,우,하,좌 의 방향을 각 0,1,2,3이라고 하고

D(i,j,d) = i,j에서 d방향으로 진행 후 M,N까지 갈 때 최소로 부수는 벽의 갯수

이렇게 알고리즘을 짰는데 질문에 올라온

5 5
01000
01010
00010
11110
00000

이 테스트 케이스가 안돌아가서 문제가 무엇인지 계속 살펴보다가 도저히 잘 모르겠어서 질문드립니다.

알고리즘이 어디가 잘 못 된 것인지 알려주시면 감사하겠습니다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
//#include <fstream>

using namespace std;
int dp[101][101][4];
bool V[101][101];
int N,M;
const int INF = 1e9;
//ofstream out("main.out");
int dy(const vector< vector<int> > &A,int x, int y, int d) {
	//out << x << " , " << y << " , " << d << endl; 
	if (x <= 0 || y <= 0 || x > M || y > N) {
		//out << INF << endl;
		return INF;
	}
	
	if (x==M && y==N) {
		//out << 0 << endl;
		return 0;
	}
	int &ret = dp[x][y][d];
	if (ret != INF) {
		//out << ret << endl;
		return ret;
	}
	V[x][y] = true;
	
	if (d==0) {
		if (A[x-1][y]==0 && !V[x-1][y]) {
			ret = min(ret,dy(A,x-1,y,0));
			ret = min(ret,dy(A,x-1,y,1));
			ret = min(ret,dy(A,x-1,y,3));
		}
		else if (A[x-1][y]==1 && !V[x-1][y]) {
			ret = min(ret,dy(A,x-1,y,0)+1);
			ret = min(ret,dy(A,x-1,y,1)+1);
			ret = min(ret,dy(A,x-1,y,3)+1);
		}
	}
	else if (d==1) {
		if (A[x][y+1]==0 && !V[x][y+1]) {
			ret = min(ret,dy(A,x,y+1,0));
			ret = min(ret,dy(A,x,y+1,1));
			ret = min(ret,dy(A,x,y+1,2));
		}
		else if (A[x][y+1]==1 && !V[x][y+1]) {
			ret = min(ret,dy(A,x,y+1,0)+1);
			ret = min(ret,dy(A,x,y+1,1)+1);
			ret = min(ret,dy(A,x,y+1,2)+1);
		}
	}
	else if (d==2) {
		if (A[x+1][y]==0 && !V[x+1][y]) {
			ret = min(ret,dy(A,x+1,y,1));
			ret = min(ret,dy(A,x+1,y,2));
			ret = min(ret,dy(A,x+1,y,3));
		}
		else if (A[x+1][y]==1 && !V[x+1][y]) {
			ret = min(ret,dy(A,x+1,y,1)+1);
			ret = min(ret,dy(A,x+1,y,2)+1);
			ret = min(ret,dy(A,x+1,y,3)+1);
		}
		
	}
	else if (d==3) {
		if (A[x][y-1]==0 && !V[x][y-1]) {
			ret = min(ret,dy(A,x,y-1,0));
			ret = min(ret,dy(A,x,y-1,3));
			ret = min(ret,dy(A,x,y-1,2));
		}
		else if (A[x][y-1]==1 && !V[x][y-1]) {
			ret = min(ret,dy(A,x,y-1,0)+1);
			ret = min(ret,dy(A,x,y-1,3)+1);
			ret = min(ret,dy(A,x,y-1,2)+1);
		}
	}
	//out << ret << endl;
	V[x][y] = false;
	return ret;
}

int main() {
	
	cin >> N >> M;
	
	vector< vector<int> > A(M+2,vector<int>(N+2));
	for (int i = 1; i <= M; ++i) {
		for (int j = 1; j <= N; ++j) {
			char inp;
			cin >> inp;
			A[i][j] = inp-'0';
		}
	}
	for (int i = 1; i <= M; ++i) {
		for (int j = 1; j <= N; ++j) {
			dp[i][j][0] = INF;
			dp[i][j][1] = INF;
			dp[i][j][2] = INF;
			dp[i][j][3] = INF;
		}
	}
	cout << min(min(min(dy(A,1,1,0),dy(A,1,1,1)),dy(A,1,1,2)),dy(A,1,1,3)) << endl;
	return 0;
}

jamrogramming 6년 전 0

dy(A, x, y, d)가 처음 호출돼서 계산될 때 그 값이 최적이라는게 보장이 안돼요.

비용이 0인 간선만 타고가서 x, y, d에 도달할 수 있는데 1인 간선을 먼저 발견하고 타버리는 경우가 생겨요.

sgchoi5 6년 전 0

두 가지를 조합해서 푸는게 제일 단순하고 일반적인 것 같습니다.

가중치가 없는 최단 경로 => BFS +

block 은 최소한으로 => dp

visited 대신에 dp table 을 이용해서 벽을 최소한으로 이용하도록 .....

문제

문제

출처

ICPC

알고리즘 질문 드립니다.

poia0304 6년 전 0

jamrogramming 6년 전 0

sgchoi5 6년 전 0

poia0304 6년 전 0

@jamrogramming

@sgchoi5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말