글 읽기 - 그리디한 접근...도와주세요

sls666 3년 전 0

- 그리디한 느낌으로 현재 위치에서 가장가까운 점으로 bfs. 그리고 그 지점을 '.'으로 바꾸고 그 지점부터 다시 bfs하는 방식으로 탐색을 시도하였습니다.

예제는 모두 통과했지만 결과는 틀렸습니다가 나오는데, 어떤 예외가 있는지..생각이 나질 않습니다.

제가 생각한 방법이 어떤 문제가 있는지 고수님들 도와주세요!

#include <iostream>
#include <queue>
#include <cstring>
#define endl '\n'
using namespace std;

const int MAX = 20;

struct Node {
	int x, y, level;
};

int N, M, sx, sy, ans;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
char map[MAX][MAX];
bool visited[MAX][MAX];


int input() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'o') {
				sx = i; sy = j;
			}
		}
	}
	return N;
}

bool bfs() {
	memset(visited, false, sizeof(visited));
	queue<Node> Q;
	Q.push({ sx, sy, 0 });
	visited[sx][sy] = true;
	ans = 0;

	while (!Q.empty()) {
		Node now = Q.front();
		Q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = now.x + dx[i];
			int ny = now.y + dy[i];

			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (map[nx][ny] == 'x') continue;
			if (map[nx][ny] == 'o') continue;
			if (visited[nx][ny]) continue;

			visited[nx][ny] = true;
			Q.push({ nx, ny, now.level + 1 });
			if (map[nx][ny] == '*') { // 더러운 점을 만났다면 이곳부터 다시 시작하기 위해 아래와 같이 세팅이 필요
				map[nx][ny] = '.';
				Q = queue<Node>();
				memset(visited, false, sizeof(visited));
				Q.push({ nx, ny, 0 });
				visited[nx][ny] = true;
				ans += now.level + 1;
				break;
			}
		}
	}

	bool ok = false;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == '*') {
				ok = true;
			}
		}
	}
	return ok;
}

void solution() {
	while (true) {
		if (input() == 0) break;
		if (bfs()) cout << -1 << endl;
		else cout << ans << endl;
	}
}

int main() {

	solution();

	return 0;
}

ghghgh777 3년 전 2

9 1

*o*.*...*

0 0

을 넣으면, 우선 54번째 줄 때문에 -1이 출력되고, 이를 지우더라도 15가 출력됩니다. (정답 : 9)

sls666 3년 전 0

아!! 감사합니다!

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

문제

문제

출처

ICPC

그리디한 접근...도와주세요

sls666 3년 전 0

ghghgh777 3년 전 2

sls666 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말