글 읽기 - [C++] 16197 백트랙킹으로 풀리던게 bfs로는 왜 안되는걸까요 ㅜㅜ.

hwang0108 4년 전 0

이 문제를 처음풀 때 백트랙킹으로 풀어서 맞았는데, bfs로 다시 한번 풀어보려고 합니다.

조건 모두 맞을 때와 동일하게 취해주었는데 왜 bfs로는 안풀리는 걸까요 ㅜㅜ.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };

int N, M;
char charMap[20][20];
int map[20][20];
vector<pair<int, int>> coins;
queue<tuple<int, int, int, int, int>> q;
bool visited[20][20][20][20];
bool isAble = false;
int res = 0;

bool oneCoinFall(int ai, int aj, int bi, int bj) {
	if ((ai < 0 || aj < 0 || ai >= N || aj >= M) || (bi < 0 || bj < 0 || bi >= N || bj >= M)) {
		return true;
	}
	else {
		return false;
	}
}

void bfs() {
	while (!q.empty()) {
		auto tmp = q.front();
		int ai = get<0>(tmp);
		int aj = get<1>(tmp);
		int bi = get<2>(tmp);
		int bj = get<3>(tmp);
		int cnt = get<4>(tmp);
		q.pop();

		if (cnt >= 10) {
			return;
		}

		for (int i = 0; i < 4; i++) {
			int ani = ai + di[i];
			int anj = aj + dj[i];
			int bni = bi + di[i];
			int bnj = bj + dj[i];

			//A코인이 벽에 부딪혔을 경우, 움직일 수 없으므로 위치 그대로.
			if (map[ani][anj] == 1) {
				ani = ai;
				anj = aj;
			}
			//B코인이 벽에 부딪혔을 경우, 움직일 수 없으므로 위치 그대로.
			if (map[bni][bnj] == 1) {
				bni = bi;
				bnj = bj;
			}

			//A,B코인이 겹쳐질 경우, 하나만 떨어트릴 해법이 없으므로 넘김.
			if (ani == bni && anj == bnj) {
				continue;
			}
			//A,B코인 모두 방문했던 곳을 갈 경우, 넘김.
			if (visited[ani][anj][bni][bnj]) {
				continue;
			}
			//A,B코인이 모두 떨어질 경우, 넘김.
			if ((ani < 0 || anj < 0 || ani >= N || anj >= M) && (bni < 0 || bnj < 0 || bni >= N || bnj >= M)) {
				continue;
			}

			if (oneCoinFall(ani, anj, bni, bnj)) {
				res = cnt + 1;
				isAble = true;
				break;
			}
			else {
				q.push({ ani,anj,bni,bnj,cnt + 1 });
				visited[ani][anj][bni][bnj] = true;
			}
		}

		if (isAble) {
			return;
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> charMap[i][j];
			if (charMap[i][j] == 'o') {
				coins.push_back({ i,j });
				map[i][j] = 0;
			}
			else if (charMap[i][j] == '#') {
				map[i][j] = 1;
			}
			else {
				map[i][j] = 0;
			}
		}
	}

	int Ai = coins[0].first;
	int Aj = coins[0].second;
	int Bi = coins[1].first;
	int Bj = coins[1].second;

	visited[Ai][Aj][Bi][Bj] = true;

	q.push({ Ai, Aj, Bi, Bj, 0 });
	bfs();

	if (isAble) {
		cout << res;
	}
	else {
		cout << -1;
	}
}

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

문제

문제

출처

ICPC

[C++] 16197 백트랙킹으로 풀리던게 bfs로는 왜 안되는걸까요 ㅜㅜ.

hwang0108 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말