반응형
문제
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
- .: 깨끗한 칸
- *: 더러운 칸
- x: 가구
- o: 로봇 청소기의 시작 위치
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
모든 더러운 지점을 다 방문하는 것의 최소이므로 기존의 BFS로는 불가.
=> 하나의 목적지가 아니므로 visit처리등에서 문제 발생.
따라서 시작점에서 더러운 지점까지 거리, 각 더러운 지점들끼리의 거리를 미리 구하고
경로의 조합중에 가장 최단 거리를 구하면 됨.
따라서 BFS+DFS를 생각하고 시도하였으나 시간초과 발생
따라서 DFS로 순열을 구하지 않고, next_permutation 사용으로 해결.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
int N, M;
char arr[20][20];
bool visit[20][20];
int dis[11][11];
bool route[11][11];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int starty, startx;
struct Node {
int y;
int x;
};
Node dirty[11];
int mina;
bool flag;
void DFS(int cur, int num, int res, int count)
{
if (num == count - 1)
{
if (mina > res)
{
mina = res;
}
return;
}
for(int i = 1; i < count; i++)
{
if (dis[cur][i] && !route[cur][i] && cur != i)
{
route[cur][i] = true;
route[i][cur] = true;
DFS(i, num + 1, res + dis[cur][i], count);
route[cur][i] = false;
route[i][cur] = false;
}
}
}
int main(void)
{
while (1)
{
cin >> M >> N;
if (N == 0 && M == 0)
{
break;
}
memset(dis, 0, sizeof(dis));
memset(dirty, 0, sizeof(dirty));
int count = 1;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> arr[i][j];
if (arr[i][j] == 'o')
{
dirty[0].y = i;
dirty[0].x = j;
arr[i][j] = '.';
}
if (arr[i][j] == '*')
{
dirty[count].y = i;
dirty[count].x = j;
count++;
}
}
}
flag = true;
for (int i = 0; i < count; i++)
{
for (int j = i + 1; j < count; j++)
{
queue<pair<Node, int> > que;
memset(visit, 0, sizeof(visit));
que.push({ {dirty[i].y,dirty[i].x},0 });
bool check = false;
while (!que.empty())
{
int y = que.front().first.y;
int x = que.front().first.x;
int cost = que.front().second;
que.pop();
if (y == dirty[j].y && x == dirty[j].x)
{
check = true;
dis[i][j] = cost;
dis[j][i] = cost;
break;
}
for (int k = 0; k < 4; k++)
{
int newy = y + dy[k];
int newx = x + dx[k];
if (newy >= 0 && newy < N && newx >= 0 && newx < M)
{
if (arr[newy][newx] != 'x' && !visit[newy][newx])
{
visit[newy][newx] = true;
que.push({ {newy,newx},cost + 1 });
}
}
}
}
if (!check)
{
flag = false;
break;
}
}
if (!flag)
{
break;
}
}
if (!flag)
{
cout << -1 << endl;
}
else
{
vector <int> location;
for (int i = 0; i < count - 1; i++)
location.push_back(i+1);
int ans = 987987987;
bool flag = true;
// [5]
do {
// 0번(로봇 청소기) -> 1번 거리
int cur = dis[0][location[0]];
if (!cur) {
// 로봇 청소기가 어떤 더러운 칸으로 가는 거리가
// 하나라도 0 이라면 바로 탈출
flag = false;
break;
}
// 1번 -> 2번 거리, 2번 -> 3번 거리, ... 를 다 더해줍니다
for (int i = 0; i < count - 2; i++) {
cur += dis[location[i]][location[i + 1]];
}
if (ans > cur) ans = cur;
} while (next_permutation(location.begin(), location.end()));
printf("%d\n", ans);
}
}
}
DFS로도 풀림 확인
대신 DFS에 넘겨주는 인자를 줄이니까 가능했다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
int N, M;
char arr[20][20];
bool visit[20][20];
int dis[11][11];
bool route[11];
int res = 0;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int starty, startx;
struct Node {
int y;
int x;
};
Node dirty[11];
int mina;
bool flag;
int C;
void DFS(int cur, int num)
{
if (num == C - 1)
{
if (mina > res)
{
mina = res;
}
return;
}
for (int i = 1; i < C; i++)
{
if (!route[i])
{
route[i] = true;
res += dis[cur][i];
DFS(i, num + 1);
res -= dis[cur][i];
route[i] = false;
}
}
}
int main(void)
{
while (1)
{
cin >> M >> N;
if (N == 0 && M == 0)
{
break;
}
memset(dis, 0, sizeof(dis));
memset(dirty, 0, sizeof(dirty));
int count = 1;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> arr[i][j];
if (arr[i][j] == 'o')
{
dirty[0].y = i;
dirty[0].x = j;
arr[i][j] = '.';
}
if (arr[i][j] == '*')
{
dirty[count].y = i;
dirty[count].x = j;
count++;
}
}
}
C = count;
flag = true;
for (int i = 0; i < count; i++)
{
for (int j = i + 1; j < count; j++)
{
queue<pair<Node, int> > que;
memset(visit, 0, sizeof(visit));
que.push({ {dirty[i].y,dirty[i].x},0 });
bool check = false;
while (!que.empty())
{
int y = que.front().first.y;
int x = que.front().first.x;
int cost = que.front().second;
que.pop();
if (y == dirty[j].y && x == dirty[j].x)
{
check = true;
dis[i][j] = cost;
dis[j][i] = cost;
break;
}
for (int k = 0; k < 4; k++)
{
int newy = y + dy[k];
int newx = x + dx[k];
if (newy >= 0 && newy < N && newx >= 0 && newx < M)
{
if (arr[newy][newx] != 'x' && !visit[newy][newx])
{
visit[newy][newx] = true;
que.push({ {newy,newx},cost + 1 });
}
}
}
}
if (!check)
{
flag = false;
break;
}
}
if (!flag)
{
break;
}
}
if (!flag)
{
cout << -1 << endl;
}
else
{
mina = 987654321;
res = 0;
memset(route, 0, sizeof(route));
for (int i = 1; i < count; i++)
{
route[i] = true;
res += dis[0][i];
DFS(i, 1);
res -= dis[0][i];
route[i] = false;
}
cout << mina << endl;
}
}
}반응형
'Algorithm' 카테고리의 다른 글
| 백준 5052번 전화번호 목록 (0) | 2020.07.14 |
|---|---|
| 백준 2151번 거울 설치 (0) | 2020.07.14 |
| 백준 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (0) | 2020.07.12 |
| 백준 17086번 아기 상어 2 (0) | 2020.07.12 |
| 백준 14426번 접두사 찾기 (0) | 2020.07.12 |