https://www.acmicpc.net/problem/14466
14466번: 소가 길을 건너간 이유 6
첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다.
www.acmicpc.net
소는 인접한 좌표로 이동할 수 있지만 길로 지정된 경로로는 길을 건너야 갈 수 있습니다.
문제에서는 길을 건너지 않으면 만날 수 없는 소의 쌍을 구하므로 "길로 지정된 경로로는 이동할 수 없다"로 접근하면 되겠습니다.
저는 소 한마리씩 이동을 하고, 이동하는 도중에 다른 소를 만난다면 카운팅을 진행하고, 전체 소의 갯수에서 제외해주는 방식으로 해결하였습니다.
저의 로직입니다.
- 2차원 pair를 이용하여 길의 정보를 넣습니다. 이 때, 양방향으로 넣어줍니다.
- 소의 좌표는 map에 인덱스를 표시해주고, 벡터에 넣어줍니다.
- 소 한마리씩 bfs로 이동하며, 주어진 길 이외에 인접한 좌표로 모두 이동시킵니다.
- 주어진 길인지 확인하는 방법은 해당 좌표에 연결된 길을 하나하나 찾는 방법을 선택하였습니다.
- 이동하는 과정에서 다른 소를 만난다면 ret을 1 증가합니다.
- 전체 소에서 ret과 1을 뺀 값을 리턴합니다. (여기서 1은 본인을 제외하는 것입니다.)
- 쌍을 구하는 문제이므로 ans/2를 출력합니다.
저는 예제가 계속 맞지않아서..
"아니 전체에서 만난 애들 뺀거랑 애초에 못만난 애들을 구한거랑 같은데 왜 다르게 나오지? 그럼 나머지 애들은 뭔데"
를 반복했었는데..
소의 수는 M인데.. 전체를 N으로 잡아서 발생한 삽질이었습니다. ^^..
저와같은 삽질을 하는 분은 없겠죠..?
|
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
|
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define MAX 101
using namespace std;
typedef pair<int, int> pii;
vector<pii> list[MAX][MAX], v;
bool visit[MAX][MAX];
int map[MAX][MAX];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, K;
int bfs(int sx, int sy) {
queue<pii> q;
visit[sx][sy] = true;
q.push({ sx,sy });
int num = map[sx][sy];
int ret = 0;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (map[x][y] && map[x][y] != num) {
ret++;
}
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 1 || ny < 1 || nx > N || ny > N) continue;
if (visit[nx][ny]) continue;
bool flag = true;
for (auto a : list[x][y]) {
if (a.first == nx && a.second == ny) {
flag = false;
break;
}
}
if (!flag) continue;
q.push({ nx,ny });
visit[nx][ny] = true;
}
}
return M - (ret + 1);
}
void func() {
int ans = 0;
int len = v.size();
for (int i = 0; i < len; i++) {
ans += bfs(v[i].first, v[i].second);
memset(visit, 0, sizeof(visit));
}
cout << ans / 2 << '\n';
}
void input() {
int sx, sy, ex, ey;
cin >> N >> M >> K;
while (K--) {
cin >> sx >> sy >> ex >> ey;
list[sx][sy].push_back({ ex,ey });
list[ex][ey].push_back({ sx,sy });
}
for (int i = 1; i <= M; i++) {
cin >> sx >> sy;
map[sx][sy] = i;
v.push_back({ sx,sy });
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 16985 Maaaaaaaaaze (0) | 2022.12.16 |
|---|---|
| boj 18112 이진수 게임 (2) | 2022.09.16 |
| boj 16946 벽 부수고 이동하기 4 (0) | 2022.05.22 |
| boj 5547 일루미네이션 (0) | 2022.05.15 |
| boj 16932 모양 만들기 (0) | 2022.05.14 |