문제 URL : https://www.acmicpc.net/problem/2842
2842번: 집배원 한상덕
상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각
www.acmicpc.net
문제 접근법 : 문제가 어려웠습니다. 여러글을 참고해서 어떻게 투포인터를 하는지 잘몰랐는데
논리를 따라가보니 이해가 되더군요
우선 dfs나 bfs로 집들을 찾는것은 쉽습니다. 범위를 찾아 최소가 되도록 하는게 관건인데
입력받은 고도내에서 범위를 찾아야합니다. 고도들이 중복될수있으니 입력받은 고도들을
정렬하여 중복을 제거하여 집합처럼 만듭니다. set을 이용해도 상관없습니다.
그렇다면 가장 작은 고도를 left와 right의 포인트를 잡아 그지점에서 시작해서 left와 right가 가리키는 고도내에서 이동이 가능한지 확인하여 모든 집을 방문할수있다면 left를 증가시키고 없다면 right를 증가시켜가며 확인하여
최소값을 저장한후 다탐색후 출력해주면 됩니다.
소스코드 :
|
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
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int n,sy,sx;
vvi board, alt, check;
int house;
vi sv;
void input() {
cin >> n;
char c;
alt = board = vvi(n, vi(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> c;
if (c == 'P') {
sy = i, sx = j;
}
else if (c == 'K') {
board[i][j] = 1;
house++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> alt[i][j];
sv.push_back(alt[i][j]);
}
}
}
bool isrange(int y, int x) { return 0 <= y && y < n && 0 <= x && x < n; }
int dfs(int y, int x, int left, int right) {
if (!isrange(y, x)) return 0;
if (check[y][x]) return 0;
check[y][x] = 1;
if (!(sv[left] <= alt[y][x] && alt[y][x] <= sv[right])) return 0;
int res = board[y][x];
for (int i = 0; i < 8; i++)
res += dfs(y + dy[i], x + dx[i], left, right);
return res;
}
void solve() {
sort(sv.begin(), sv.end());
sv.erase(unique(sv.begin(), sv.end()), sv.end());
int left = 0;
int res = 1e9;
for (int right = 0; right < sv.size(); right++) {
while (left<=right&&left < sv.size()) {
check = vvi(n, vi(n));
if (dfs(sy, sx, left, right) != house)
break;
res = min(res, sv[right] - sv[left]);
left++;
}
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤 질문이든 댓글은 언제나 환영입니다.
공감 눌러주실꺼죠??
'백준' 카테고리의 다른 글
| 백준 6324 URLs (0) | 2021.09.01 |
|---|---|
| 백준 1938 통나무 옮기기 (0) | 2021.08.31 |
| 백준 2505 두 번 뒤집기 (0) | 2021.08.26 |
| 백준 17267 상남자 (0) | 2021.08.26 |
| 백준 1942 디지털 시계 (0) | 2021.08.23 |
