[BOJ][실1][1058] 친구

문제 링크

문제링크

첫 번째 풀이 : DFS

알고리즘

dfs를 사용해서 풀어보겠습니다. a,b,c가 있다고 해보겠습니다. a와 b가 친구이기 위해서는 두 가지 경우가 존재합니다.

1. a와 b가 직접 친구이다.
2. a와 c가 친구이고, c와 b가 친구이다.

답을 구하기 위해서는 각각의 사람들이 누구와 친구인지 인접리스트로 저장을 합니다. 그리고 한 명씩 돌아가면서 각자의 2친구를 최대한 많이 찾습니다. 직접 친구로만 구성된 인접리스트를 구성해두고, 이것을 이용해서 깊이가 2일때까지만 dfs를 진행하면 됩니다. 단, 시작하는 노드는 자기 자신이기 때문에 정답을 출력할 때는 -1을 합니다.

a와 b가 친구인지 판단하기 위해서 a와 b 모두와 친구인 c가 있는지 판단할 때, a와 친구가 아닌 모든 사람들은 테스트하지 않아도 됩니다. a와 b가 친구이기 위한 두 번째 경우에서 c가 a의 친구인지 판단하기 위해서 친구로만 구성된 인접리스트를 사용해도 문제가 없습니다. a와 c가 친구이기 위해서는 중간에 둘 다와 친구인 b가 존재한다는 뜻이고, 다시 말하면 결국 b는 a와 친구입니다. 따라서 친구로만 구성된 인접리스트에서 깊이가 2일때까지만 dfs를 진행하면 됩니다.

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> v[50];
bool visited[50];
int ans = 0;
int tans = 0;

void dfs(int x, int depth) {
  if (!visited[x]) {
    visited[x] = true;
    tans++;
  }
  if (depth == 2) {
    return;
  }

  for (int i = 0; i < v[x].size(); i++) {
    int next = v[x][i];
    dfs(next, depth + 1);
  }
}

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  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++) {
    tans = 0;
    memset(visited, false, sizeof(visited));
    dfs(i, 0);
    ans = max(ans, tans);
  }
  cout << ans - 1 << "\n";

  return 0;
}

두 번째 풀이 : 구현

i와 2친구인 사람 j를 찾아야 합니다. i와 j가 친구인 경우, i와 j가 친구는 아니지만 i와 k가 친구이고 k와 j가 친구인 경우를 찾습니다.

i와 j가 친구이고 j와 k가 친구일 때 i와 k가 2친구는 아닙니다!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char v[50][50];
bool visited[50];
int ans = 0;

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> v[i][j];
    }
  }

  // i와 j가 친구인 경우를 count
  for (int i = 0; i < n; i++) {
    int tans = 0;
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      if (v[i][j] == 'Y') tans++;
      else {
        for (int k = 0; k < n; k++) {
          if (v[i][k] == 'Y' && v[k][j] == 'Y') {
            tans++;
            break;
          }
        }
      }
    }
    ans = max(ans, tans);
  }
  cout << ans << "\n";
  return 0;
}

세 번째 풀이 : BFS

정석적인 BFS는 아니지만 너비 1인 경우와 너비 2인 경우를 따져서 생각하는 방법으로 풀이한 경우입니다. 구현 풀이와 유사합니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char v[50][50];
bool visited[50];
int ans = 0;
int n;
int bfs(int i) {
  memset(visited, false, sizeof(visited));
  int tans = 0;
  queue<int> q;
  visited[i] = true;
  // i 빼고 모두 queue에 넣기
  for (int x = 0; x < n; x++) {
    if (i != x) q.push(x);
  }
  while (!q.empty()) {
    int j = q.front(); q.pop();
    if (!visited[j]) {
      // 바로 친구인 경우 (너비 1)
      if (v[i][j] == 'Y')
      {
        tans++;
        visited[j] = true;
      }
      else {
        // 건너 친구인 경우 (너비 2)
        for (int k = 0; k < n; k++) {
          if (v[i][k] == 'Y' && v[k][j] == 'Y') {
            tans++;
            visited[j] = true;
            break;
          }
        }
      }
    }
  }
  return tans;
}

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> v[i][j];
    }
  }

  for (int i = 0; i < n; i++) {
    ans = max(ans, bfs(i));
  }

  cout << ans << "\n";
  return 0;
}

Success Notice: 수고하셨습니다.