글 읽기 - [4991 - 로봇청소기] 질문드립니다..

morpheus 4년 전 0

안녕하세요 로봇청소기를 풀다가 헤매고 있는 코딩초보입니다ㅠㅠ

제가 짠 코드의 로직은 이렇습니다.

1. 각 먼지들에 순서대로 1부터 번호를 부여

2. 로봇청소기에 대해 bfs를 실행하여 모든 먼지들까지의 최단거리를 DP배열(인덱스는 0)에 저장

(만약 여기서 도달할 수 없는 먼지가 있으면 바로 -1을 출력하고 리턴)

3. 각 먼지들끼리 bfs를 실행하여 서로에 대한 최단거리를 DP배열(인덱스는 각 먼지들에 부여된 번호)에 저장

4. 순열을 활용하여 로봇에서부터 시작하여 모든 경로에 대한 최단거리를 계산

로직이 잘못된건지 코드가 잘못된건지 현재로썬 감이 잘 안오네요..

반례나 코드에 오류가 있으면 지적 부탁드립니다!!

#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

int drow[4] = { 0, -1, 0, 1 };
int dcol[4] = { -1, 0, 1, 0 };

int h, w, dustCnt;	// dustCnt는 먼지의 개수
char matrix[20][20];
int dustNum[10];	// 순열에 사용될 먼지들의 번호를 순서대로 저장

/* 첫번째 차원의 0번 인덱스는 로봇이 사용 */
int dist[11][20][20];	// bfs에서 사용
bool visited[11][20][20];
int DP[11][11];			// 각 먼지사이끼리의 최단거리 저장

void bfs(int start_r, int start_c, int num)
{
	int r, c, nr, nc;
	queue<pair<int, int>> Q;

	visited[num][start_r][start_c] = 1;
	Q.push({ start_r, start_c });
	while (!Q.empty())
	{
		r = Q.front().first;
		c = Q.front().second;
		Q.pop();
		for (int i = 0; i < 4; i++)
		{
			nr = r + drow[i];
			nc = c + dcol[i];
			if (nr >= h || nr < 0 || nc >= w || nc < 0)	continue;
			if (visited[num][nr][nc] == 0 && matrix[nr][nc] != 'x')
			{
				visited[num][nr][nc] = 1;
				dist[num][nr][nc] = dist[num][r][c] + 1;
				if (matrix[nr][nc] >= '1' && matrix[nr][nc] <= '10')	// 먼지를 만났을 경우
				{
					DP[num][matrix[nr][nc] - '0'] = dist[num][nr][nc];	// 최단거리 저장
				}
				Q.push({ nr, nc });
			}
		}
	}
}

int main()
{
	int robot_r, robot_c;	// 로봇의 위치
	int dust_r, dust_c;		// 먼지의 위치
	vector<pair<int, int>> dustList;    // 먼지의 위치를 저장하는 리스트
	while (true)
	{
		/* 초기화 작업 */
		for (int i = 0; i < 11; i++)
		{
			memset(DP[i], 0, sizeof(DP[i]));
			for (int j = 0; j < 20; j++)
			{
				memset(dist[i][j], 0, sizeof(dist[i][j]));
				memset(visited[i][j], 0, sizeof(visited[i][j]));
			}
		}
		dustList.clear();
		dustCnt = 0;

		/* 값 입력 */
		cin >> w >> h;
		if (w == 0 && h == 0)	break;
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				cin >> matrix[i][j];
				/* 로봇청소기 및 먼지의 위치 저장 */
				if (matrix[i][j] == 'o')
				{
					robot_r = i;
					robot_c = j;
				}
				else if (matrix[i][j] == '*')	// 각각의 먼지에 1부터 번호를 매긴 후 좌표를 리스트에 삽입
				{
					matrix[i][j] = ++dustCnt + '0';	
					dustNum[dustCnt - 1] = dustCnt;
					dustList.push_back({ i, j });
				}
			}
		}

		bfs(robot_r, robot_c, 0);	// 로봇 청소기에 대해 bfs

		/* 도달할 수 없는 먼지가 있는지 확인 */
		bool flag = true;
		for (int i = 1; i <= dustCnt; i++)
		{
			if (DP[0][i] == 0)
			{
				flag = false;
				break;
			}
		}
		if (flag == false)
		{
			cout << -1 << '\n';	// 도달할 수 없는 먼지가 존재하면 -1 출력 후 리턴
			return 0;
		}

		for (int i = 0; i < dustCnt; i++)	// 각 먼지들에 대해 bfs
		{
			dust_r = dustList[i].first;
			dust_c = dustList[i].second;
			bfs(dust_r, dust_c, matrix[dust_r][dust_c] - '0');
		}

		/* 최단경로를 순열을 통해 계산 */
		int res = INT32_MAX;
		do
		{
			int sum = DP[0][dustNum[0]];
			for (int i = 1; i < dustCnt; i++)
			{
				sum += DP[dustNum[i - 1]][dustNum[i]];
			}
			res = min(res, sum);
		} while (next_permutation(dustNum, &dustNum[dustCnt]));
		cout << res << '\n';	// 결과 출력
	}
	return 0;
}

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

문제

문제

출처

ICPC

[4991 - 로봇청소기] 질문드립니다..

morpheus 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말