반응형

https://www.acmicpc.net/problem/4991

 

4991번: 로봇 청소기

각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 먼지 간의 거리를 저장할 dist [ i ][ j ] 배열을 만듭니다.

 

2. dist 배열을 만들어 먼지의 위치를 저장합니다.

 

3. dfs를 통해 각 지점까지 이동하는 모든 경우의 수를 뽑고, 마지막에 이동 거리 중 가장 적은 값을 ans에 저장합니다.

 

4. ans를 출력하고, 만약 이동할 수 없는 곳이 있다면 -1을 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
 
using namespace std;
 
int w, h;
char arr[21][21];
int visited[10];
int dist[10][10];    //i부터 j까지 거리
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int ans;
vector<pair<int, int>> dirt;
 
struct pos {
    int y;
    int x;
    int cnt;
};
 
int bfs(int from, int to)    //시작점부터 도착점까지 거리
{
    queue<pos> q;
    int visited[21][21] = { 0 };
 
    q.push({ dirt[from].first,dirt[from].second,0 });
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int cnt = q.front().cnt;
        q.pop();
 
        if (y == dirt[to].first && x == dirt[to].second) {
            return cnt;
        }
 
        if (visited[y][x] == 1) continue;
        visited[y][x] = 1;
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < h && xx >= 0 && xx < w) {
                if (visited[yy][xx] != 1 && arr[yy][xx] != 'x') {
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
 
    return -1;
}
 
void dfs(int level, int cur, int hap)    //cur부터 i까지 거리를 hap에 저장
{
    if (ans == -1) return;
 
    if (level == dirt.size() - 1) {
        ans = min(ans, hap);
        return;
    }
 
    for (int i = 1; i < dirt.size(); i++) {
        if (visited[i] != 1) {
            visited[i] = 1;
            if (dist[cur][i] == -1) {
                dist[cur][i] = bfs(cur, i);
            }
            dist[i][cur] = dist[cur][i];
            if (dist[cur][i] == -1) {
                ans = -1;
                return;
            }
            hap += dist[cur][i];
            dfs(level + 1, i, hap);
            hap -= dist[cur][i];
            visited[i] = 0;
        }
    }
}
 
int main()
{
    while (1) {
        scanf("%d %d", &w, &h);
 
        if (w == 0 && h == 0) break;
 
        dirt.clear();
        dirt.emplace_back(0, 0);
        ans = 987654321;
        memset(dist, -1, sizeof(dist));
 
        for (int i = 0; i < 10; i++) {
            visited[i] = 0;
        }
 
        for (int i = 0; i < h; i++) {
            scanf("%s", arr[i]);
        }
 
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (arr[i][j] == 'o') {
                    dirt[0].first = i;
                    dirt[0].second = j;
                }
                if (arr[i][j] == '*') {
                    dirt.emplace_back(i, j);
                }
            }
        }
 
        dfs(0, 0, 0);
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 17182번 - 우주 탐사선 (C++)  (0) 2022.11.27
[ 백준 ] 15591번 - MooTube (Silver) (C++)  (0) 2022.11.26
[ 백준 ] 6087번 - 레이저 통신 (C++)  (0) 2022.11.24
[ 백준 ] 4485번 - 녹색 옷 입은 애가 젤다지? (C++)  (0) 2022.11.23
[ 백준 ] 2151번 - 거울 설치 (C++)  (0) 2022.11.22

+ Recent posts

티스토리툴바