글 읽기 - BFS 이용하여...

shaing123 5년 전 0

제 로직을 말씀드리자면 로봇의 위치와 더러운칸 사이에 거리를 bfs를 사용하여 계산하여

dis 벡터에 저장하였습니다.

또한 더러운칸에서 다른 더러운칸이나 로봇의 거리까지도 bfs를 통하여 각 더러운칸마다 bfs를 돌려 dis벡터에 저장하

였습니다.

이를 토대로 로봇의위치는 index 0으로 고정하고 나머지를 순열을 이용하여 최솟값을 찾았습니다.

어느 부분에서 간과하고 지나갔는지... 조언 좀 부탁드립니다. 반례도 부탁 드리겠습니다..

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#include<tuple>
using namespace std;
int w, h;
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
char map[21][21];
//로봇의 위치 및 더러운 칸의 위치
vector<pair<int, int> > dir(1);
//시작 벡터 index, 도착 벡터 index, 그 사이의 거리
vector<tuple<int, int, int> > dis;
void bfs(int x, int y, int order) {
	int check[21][21] = { 0, };
	int d[21][21] = { 0, };
	check[x][y] = true;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	d[x][y] = 0;
	while (!q.empty()) {
		int nowx = q.front().first, nowy = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = nowx + dx[i], ny = nowy + dy[i];
			if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
				if (check[nx][ny] == false && map[nx][ny] != 'x') {
					check[nx][ny] = true;
					q.push(make_pair(nx, ny));
					d[nx][ny] = d[nowx][nowy] + 1;
				}
			}
		}
	}
	//s로부터 도착 지점, 거리 정보를 저장한다.
	for (int i = 0; i < dir.size(); i++) {
		if (x == dir[i].first && y == dir[i].second) continue;
		dis.push_back(tie(order, i, d[dir[i].first][dir[i].second]));
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	while (true) {
		cin >> w >> h;
		if (h == 0 && w == 0)	break;
		//맵의 정보를 받아 로봇의 위치와 더러운방의 위치를 저장
		for (int i = 0; i < h; i++) {
			cin >> map[i];
			for (int j = 0; j < w; j++) {
				if (map[i][j] == 'o') {
					dir[0] = make_pair(i, j);
				}else if (map[i][j] == '*') 
					dir.push_back(make_pair(i, j));
			}
		}
		//로봇에서 각 더러운칸의 거리, 각 더러운칸에서 다른 더러운칸의 거리 정보 계산
		vector<int> order(dir.size());
		for (int i = 0; i < dir.size(); i++) {
			bfs(dir[i].first, dir[i].second, i);
			order[i] = i;
		}
		int ans = 999999;
		do {
			int temp = 0;
			for (int i = 0; i < dir.size() - 1; i++) {
				for (int j = 0; j < dis.size(); j++) {
					if (order[i] == get<0>(dis[j]) && order[i+1] == get<1>(dis[j])) {
						temp += get<2>(dis[j]);
						break;
					}
				}
			}
			if (ans > temp) ans = temp;
		} while (next_permutation(order.begin() + 1 , order.end()));
		if (ans == 0)	cout << -1 << '\n';
		else cout << ans << '\n';
		dir.clear();
		dis.clear();
		memset(map, 0, sizeof(map));
	}
}

shaing123 5년 전 7

반례는 https://icpc.iisf.or.jp/past-i...에서 찾았으며

13라인에 벡터를 초기화하는것을 main함수 내부로 넣었습니다. 그 이유는 처음 while문 이후로는 dir[0]이 로봇의 위치를 항상 갖지않는다는 것을 간과하였습니다.

또한 순열에서 이중포문으로 시간을 많이 잡아먹어 고생하였습니다.

2차원 배열을 통하여 2중포문은 하나의 for문으로 변경하여 성공하였습니다.

혹여 도움이 될까 스스로 답변 달아 봅니다.

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

문제

문제

출처

ICPC

BFS 이용하여...

shaing123 5년 전 0

shaing123 5년 전 7

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말