티스토리 뷰
반응형
https://www.acmicpc.net/problem/4991
4991번: 로봇 청소기
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
www.acmicpc.net
필요한 배경지식
- 1번 풀이 : DFS, BFS
- 2번 풀이 : BFS, 외판원 문제(TSP)
- 3번 풀이 : BFS, DP, 비트마스킹
문제 해결 방법
방의 크기가 최대 20*20이므로 최단경로를 구하기 위해 BFS를 한번 수행하는 시간은 크게 문제가 되지 않습니다.
더러운 칸의 개수가 10개이므로 BFS를 최대 11번 수행하여 모든 더러운 칸과 로봇청소기 사이의 거리를 어렵지 않게 구할 수 있습니다. (dist 배열)
(풀이 1)
우선 최소 이동 횟수를 구하기 위해 완전탐색을 생각해 볼 수 있습니다.
위에서 구한 최단 경로를 이용하여 모든 더러운 칸의 방문 순서를 정하는데에 dfs를 이용한다면 총 개수는 10!이고 이는 충분히 시간안에 들어올 수 있는 풀이입니다.
(풀이 2)
모든 더러운 칸과 로봇청소기 시작점 사이의 경로 중 하나라도 방문할 수 없는 경로가 있다면 -1을 출력하면 되지만 모두 방문을 할 수 있다면 위에서 설명한 것 처럼 모든 최단경로를 구해낼 수 있고 이것은 완전그래프로 표현될 수 있습니다. 이때 모든 노드를 방문할 최단 경로를 찾아야 하는데 이러한 문제는 외판원 문제(traveling salesman problem)로 잘 알려져 있습니다. 방문해야 할 노드의 개수가 N개일때 시간복잡도는 O(2^N * N^2)이므로 풀이중 가장 빠른 시간안에 문제를 해결할 수 있습니다.
(풀이 3)
방문을 확인하는 배열크기를 늘리고 단순 BFS로 풀어낼 수도 있습니다.
백준에서 풀어볼 수 있는 문제들 중 BFS와 DP 태그가 붙은 최단경로를 구해내는 문제들과 같은 방법입니다.
방문처리하는 배열이 visited[r][c][k] 일때 r과 c는 방의 위치를 의미하며 k는 방문한 더러운 칸의 정보를 비트마스킹으로 표현한 것을 의미합니다. 이렇게 정의하면 로봇이 항상 같은 크기로 이동하므로 단순 BFS로 문제를 간결하게 해결할 수 있습니다.
1. DFS , BFS 풀이 코드
2. BFS , TSP(바텀업) 풀이 코드
<hide/>
#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using pii = pair<int,int>;
using tpi = tuple<int,int,int>;
const int INF = 0x3f3f3f3f;
int N,M, K, sty, stx;
int m[20][20]{};
pii v[11]{};
int dp[11][1<<10]{};
int dist[11][11]{};
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};
bool bfs(int st){
int vi[20][20]{};
memset(vi,-1,sizeof(vi));
queue<tpi> q;
q.push({0, v[st].xx, v[st].yy});
vi[v[st].xx][v[st].yy] = 0;
while(!q.empty()){
int cd, cy, cx;
tie(cd, cy, cx) = q.front();
q.pop();
for(int i=0; i<4; i++){
int nd = cd + 1;
int ny = cy + dy[i];
int nx = cx + dx[i];
if(ny<0 || nx<0 || ny>=N || nx>=M || vi[ny][nx]!=-1 || m[ny][nx]==-1) continue;
q.push({nd, ny, nx});
vi[ny][nx] = nd;
}
}
for(int i=0; i<=K; i++){
dist[st][i] = vi[v[i].xx][v[i].yy];
if(dist[st][i] == -1) return false;
}
return true;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int tt = 0;
while(1){
tt++;
cin>>M>>N;
if(!N) break;
memset(m,-1,sizeof(m));
memset(dp,0x3f,sizeof(dp));
K=0;
string str;
for(int i=0; i<N; i++){
cin>>str;
for(int j=0; j<M; j++){
if(str[j] == 'o') v[0].xx = i, v[0].yy = j, m[i][j] = 0;
else if(str[j] == '*') m[i][j] = ++K, v[K].xx = i, v[K].yy = j;
else if(str[j] == 'x') m[i][j] = -1;
else m[i][j] = 0;
}
}
bool chk = true;
for(int i=0; i<=K; i++) {
if(!bfs(i)) {
chk = false;
break;
}
}
if(!chk) {
cout<<-1<<'\n';
continue;
}
dp[0][0] = 0;
for(int mask=1; mask<(1<<K); mask++){
for(int i=1; i<=K; i++){
if(mask & (1<<(i-1))) {
int pre = mask ^ (1<<(i-1));
for(int j=0; j<=K; j++){
if(dp[j][pre] >= INF) continue;
dp[i][mask] = min(dp[i][mask], dp[j][pre] + dist[j][i]);
}
}
}
}
int res = INF;
for(int i=1; i<=K; i++){
res = min(res, dp[i][(1<<K)-1]);
}
cout<<res<<'\n';
}
}
3. BFS + DP(비트마스킹) 풀이 코드
<hide/>
#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using pii = pair<int,int>;
using dpi = pair<pii,pii>;
int N,M;
int m[20][20]{};
bool vi[20][20][1<<10]{};
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};
int bfs(int sty, int stx, int K){
memset(vi,0,sizeof(vi));
queue<dpi> q;
q.push({{0,0}, {sty,stx}});
vi[sty][stx][0] = false;
while(!q.empty()){
int cd = q.front().xx.xx;
int ck = q.front().xx.yy;
int cy = q.front().yy.xx;
int cx = q.front().yy.yy;
q.pop();
if(ck == (1<<K)-1) return cd;
for(int i=0; i<4; i++){
int nd = cd + 1;
int nk = ck;
int ny = cy + dy[i];
int nx = cx + dx[i];
if(ny<0 || nx<0 || ny>=N || nx>=M || m[ny][nx]==-1) continue;
if(m[ny][nx] > 0) nk |= (1<<(m[ny][nx]-1));
if(vi[ny][nx][nk]) continue;
q.push({{nd,nk}, {ny,nx}});
vi[ny][nx][nk] = true;
}
}
return -1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
while(1){
cin>>M>>N;
if(!N) break;
memset(m,-1,sizeof(m));
int sty, stx, K=0;
string str;
for(int i=0; i<N; i++){
cin>>str;
for(int j=0; j<M; j++){
if(str[j] == 'o') sty = i, stx = j, m[i][j] = 0;
else if(str[j] == '*') m[i][j] = ++K;
else if(str[j] == 'x') m[i][j] = -1;
else m[i][j] = 0;
}
}
cout<<bfs(sty, stx, K)<<'\n';
}
}
반응형
'알고리즘 공부 > 문제풀이' 카테고리의 다른 글
| 백준 14226번 - 이모티콘 (0) | 2021.07.10 |
|---|---|
| 백준 1017번 - 소수 쌍 (0) | 2021.06.09 |
| 백준 17142번 - 연구소 3 (0) | 2021.05.31 |
| 백준 2342번 - Dance Dance Revolution (0) | 2021.05.31 |
| 백준 15957번 - 음악 추천 (4) | 2021.05.29 |