반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 성적평가
- compose
- 이분탐색
- Docker
- upper_bound
- 연결요소
- 경력
- BOJ
- OFFSET
- incr
- 6987
- msSQL
- Kafka
- 13908
- 백트래킹
- 처우협의
- boj #19237 #어른 상어
- BFS
- 오퍼레터
- 백준
- @P0
- 기술면접
- dfs
- 물채우기
- 소프티어
- 처우산정
- 퇴사통보
- softeer
- 파라메트릭
- 매개변수탐색
Archives
- Today
- Total
기술 블로그
1058번 친구 본문
728x90
반응형
https://www.acmicpc.net/problem/1058
dfs 풀려고 했는데, 계속 틀렸다고 나와서
플로이드-와샬, bfs로 풀었다.
내가 푼 dfs에서는 반례가 있었다.
1 2 3 4 5 6 7 | 6 NYYNYN YNYNNN YYNYNN NNYNNN YNNNNY NNNNYN | cs |
위의 예시 경우
0 → 1 → 2를 한 다음
0 → 2 → 3을 해야하는데 이미 전에 2를 방문처리(true)로 해버려서
3을 방문하지 못 한다.
따라서, 좀 더 좋은(?) dfs를 설계해야 한다.
이 부분은 나중에..
dfs(오답)
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 | #include <bits/stdc++.h> using namespace std; #define Max 55 int n, ans = -1; vector<int> v[Max]; bool visit[Max]; int dfs(int now, int len) { visit[now] = true; // 방문 처리 if (len >= 2) return 0; // 거리가 2 이상인 정점까지 도달했으면 return int ret = 0; for (auto next : v[now]) { if (!visit[next]) { ret += dfs(next, len + 1) + 1; // 정점 방문할 때마다 +1 } } return ret; } int main() { //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin); cin.tie(0); scanf("%d", &n); getchar(); char c; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> c; if (c == 'Y') { v[i].push_back(j); } } } for (int i = 0; i < n; i++) { memset(visit, false, sizeof(visit)); ans = max(ans, dfs(i, 0)); } printf("%d\n", ans); return 0; } | cs |
BFS(정답)
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 | #include <bits/stdc++.h> using namespace std; #define Max 55 int n, ans = -1; vector<int> v[Max]; bool visit[Max]; int bfs(int start) { memset(visit, false, sizeof(visit)); visit[start] = true; queue<pair<int, int> > q; q.push({ start, 0 }); while (!q.empty()) { int qs = q.size(); while (qs--) { int here = q.front().first; int len = q.front().second; q.pop(); if (len >= 2) { continue; } for (auto next : v[here]) { if (!visit[next]) { visit[next] = true; q.push({ next, len + 1 }); } } } } int ret = 0; for (int i = 0; i < n; i++) { if (visit[i] && i != start) { ++ret; } } return ret; } int main() { //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin); cin.tie(0); scanf("%d", &n); getchar(); char c; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> c; if (c == 'Y') { v[i].push_back(j); } } } for (int i = 0; i < n; i++) { ans = max(ans, bfs(i)); } printf("%d\n", ans); return 0; } | cs |
플로이드-와샬(정답)
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 | #include <bits/stdc++.h> using namespace std; #define INF 987654321 #define Max 55 int n, ans, fw[Max][Max]; int main() { //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin); cin.tie(0); scanf("%d", &n); getchar(); char c; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> c; if (i == j) fw[i][j] = 0; else if (c == 'Y') { fw[i][j] = 1; } else { fw[i][j] = INF; } } } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (fw[i][j] > fw[i][k] + fw[k][j]) { fw[i][j] = fw[i][k] + fw[k][j]; } } } } for (int i = 0; i < n; i++) { int cnt = 0; for (int j = 0; j < n; j++) { if (fw[i][j] <= 2) { ++cnt; } } ans = max(ans, cnt - 1); } printf("%d\n", ans); return 0; } | cs |
728x90
반응형
'알고리즘 문제 > BOJ' 카테고리의 다른 글
2352번 반도체 설계 (0) | 2020.01.04 |
---|---|
17267번 상남자 (0) | 2020.01.03 |
1449번 수리공 항승 (0) | 2020.01.02 |
18244번 변형 계단 수 (0) | 2020.01.01 |
10844번 쉬운 계단 수 (0) | 2020.01.01 |