#include<iostream>
using namespace std;
int t, n, d[2][100002];
int max(int a, int b){
return ((a < b) ? b : a);
}
int main(void){
cin >> t;
while (t--){
cin >> n;
int a, b;
for (int i = 0; i < 2; i++)
for (int j = 1; j <= n; j++)
cin >> d[i][j];
for (int i = 2; i <= n; i++){
d[0][i] += max(d[1][i - 1], d[1][i - 2]);
d[1][i] += max(d[0][i - 1], d[0][i - 2]);
}
cout << max(d[0][n], d[1][n]) << "\n";
}
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
단순히 모든 정점을 방문한다고 생각해서 friends[i][k] == 'Y' && frineds[k][j] == 'Y' 라고 하면
플로이드에서 0 -(N)-> 0 -(Y)-> 1 인 경우 친구가 아니라고 판단하게 됨
또한, 0 -(Y)-> 1 -(Y)-> 0 인경우는 friends[0][0] 을 친구로 만들어 버림
friends 를 업데이트 하게 되면 A-B-C-D 에서 A-D가 친구로 판단 하기 때문에 다른 친구관계를 저장할 다른 배열이 필요함
- 3가지 경우로 나눠야 함
ⅰ) A -(N)-> A -(Y)-> B 인 경우
i == k && friends[k][j] == 'Y'
ⅱ) A -(Y)-> B -(N)-> B 인 경우
k == j && friends[i][k] == 'Y'
ⅲ) 일반적인 경우 A -(Y)-> B -(Y)-> C
friends[i][k] == 'Y' && friends[k][j] == 'Y'
※ 나머지
0 -(Y)-> 1 -(Y)-> 0 으로 돌아오는 경우는 새로 만들어 주는 배열에서 친구관계를 셀때 빼면됨
플로이드는 경로가 출발, 도착 보다 뒤에 바뀌기 때문에 책처럼 풀 수 없음
0 -> 1 -> 2 다음엔 0 -> 1 -> 3 ... 1 -> 1 -> 3 이런 순이기 때문에 한 정점에서 시작하는 모든 친구를 셀 수 없음
- dfs 는
1
0 < |
2 - 3
인 경우에 0 - 1 - 2 순으로 방문하면 정점 2는 방문 했기 때문에 더이상 방문을 하지 못함
하지만 최단거리(친구 2단계) 에서는 0 - 2 - 3 으로 0과 3이 친구가 될 수 있음
- bfs 는 깊이(친구 2단계)를 지정해주면 풀 수있음
소스코드 : 플로이드
#include<iostream>
#include<string>
#include<vector>
using namespace std;
class FriendScore{
public:
int highestScore(vector <string> friends){
int ans = 0; int n = friends[0].size();
vector<vector<bool> > map(n, vector<bool>(n, false));
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if ((i == k && friends[k][j] == 'Y') || (k == j && friends[i][k] == 'Y') || (friends[i][k] == 'Y' && friends[k][j] == 'Y'))
map[i][j] = true;
for (int i = 0; i < n; i++){
int temp = 0;
for (int j = 0; j < n; j++){
if (i != j && map[i][j]) temp++;
}
if (ans < temp) ans = temp;
}
return ans;
}
};
소스코드 : bfs
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
class FriendScore{
public:
int highestScore(vector <string> friends){
int ans = 0;
vector<bool> check;
queue<pair<int, int> > q;
for (int i = 0; i < friends[0].size(); i++){
check = vector<bool>(friends[0].size(), false);
check[i] = true;
q.push(make_pair(i, 0));
int temp = 0;
while (!q.empty()){
int now = q.front().first;
int deep = q.front().second;
q.pop();
for (int j = 0; j < friends[0].size(); j++){
if (deep < 2 && !check[j] && friends[now][j] == 'Y'){
check[j] = true;
q.push(make_pair(j, deep + 1));
temp++;
}
}
}
if (ans < temp) ans = temp;
}
return ans;
}
};
