[BOJ] 3485 - Play on Words

https://www.acmicpc.net/problem/3485

BOJ - Play on Words

문제 유형: 그래프 이론, 오일러 경로, 오일러 회로, dfs

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 256MB

 

문제

Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.

There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word "acm" can be followed by the word "motorola". Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.

 

비밀의문의 일부는 매우 흥미로운 단어 퍼즐을 가지고 있습니다.

고고학자들은 문을 열려고 합니다.

다른 방법은 없기에, 이 퍼즐이 매우 중요합니다.

 

수많은 자석 플레이트가 문마다 있습니다. 이들을 나열해야 합니다.

각 플레이트는 하나의 단어가 적혀 있고, 다음 플레이트의 단어의 시작은 이전 플레이트의 단어의 끝과 일치해야 합니다.

당신이 이 플레이트들로 나열해서 퍼즐을 풀 수 있는건지 알아내도록 도와줘야 합니다.

 

입력

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number N that indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list.

 

첫째 줄에 테스트케이스의 개수 T가 주어집니다.

각 테스트케이스의 첫 번째 줄은 플레이트의 개수 N(1 <= N <= 100000)이 주어집니다.

그리고 이후 N개의 줄에는 플레이트에 쓰여진 단어가 나옵니다. 같은 단어가 여러 번 나올 수도 있습니다.

1000자 이하의 영문소문자 단어입니다.

 

출력

Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.

If there exists such an ordering of plates, your program should print the sentence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.".

 

각 테스트 케이스에 대해서 모든 플레이트를 나열할 수 있는지를 판별해야 합니다.

가능하면 "Ordering is possible", 불가능하면 "The door cannot be opened"를 출력하면 됩니다.

 

풀이

단어들을 방향그래프로 나타낼 수 있다.

즉, "acm"은 노드 'a'에서 'm'으로 향하는 간선이라고 볼 수 있다. 노드는 26개 고정이 되겠다.

각 단어들을 이렇게 파싱하여 진출차수 및 진입차수 정보, 그리고 인접 행렬을 만든다. adj[u][v] = <경로의 개수>로 한다.

그러고, 이 모든 간선들을 한 번에 순회할 수 있어야 한다. 즉, 그래프에서 한붓그리기가 되어야 한다.

 

오일러 경로/회로가 그래프에서 존재하는지 찾으면 된다.

우선, 진출차수와 진입차수는 모두 같거나, 진출차수가 하나 더 많은 노드 하나와 진입차수가 하나 더 많은 노드 하나씩만 있어야 한다.

그렇지 않으면, 오일러 경로/회로가 아니다. 즉, 이 조건을 불만족할 시 빠르게 나열 불가능을 판단할 수 있다.

 

만약 이 조건이 맞는다면, 그래프가 한 컴포넌트로 이어져있는지와, 시작점(오일러 경로인 경우 진출차수가 하나 더 많은 노드, 또는 오일러 회로인 경우 노드 아무곳에서)에서 dfs를 하여 모든 간선을 방문처리할 수 있어야 한다.

시작점에서 dfs를 하여 모든 간선을 거쳤다면, 오일러 회로/경로이므로, 플레이트 나열이 가능하다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

void dfs(int node, vector<vector<int>> &adj) {
  for (int i = 0; i < 26; ++i) {
    if (adj[node][i] > 0) {
      adj[node][i]--;
      dfs(i, adj);
    }
  }
}

bool isConnected(vector<int> &indegree, vector<int> &outdegree,
                 vector<vector<int>> &adj) {
  // check if it is eulerian path
  int startNode = -1;
  int endNode = -1;
  for (int i = 0; i < 26; ++i) {
    int cmp = outdegree[i] - indegree[i];
    if (cmp == 1) {
      if (startNode == -1)
        startNode = i;
      else
        return false;
    } else if (cmp == -1) {
      if (endNode == -1)
        endNode = i;
      else
        return false;
    } else if (cmp != 0)
      return false;
  }

  if (startNode == -1) {
    for (int i = 0; i < 26; ++i) {
      if (outdegree[i] > 0) {
        startNode = i;
        break;
      }
    }
  }
  dfs(startNode, adj);
  for (int i = 0; i < 26; ++i) {
    for (int j = 0; j < 26; ++j) {
      if (adj[i][j] > 0)
        return false;
    }
  }
  return true;
}

void solve() {
  int n;
  cin >> n;
  vector<int> outdegree(26, 0);
  vector<int> indegree(26, 0);
  vector<vector<int>> graph(26, vector<int>(26, 0));
  string temp;
  for (int i = 0; i < n; ++i) {
    cin >> temp;
    int first = temp[0] - 'a';
    int last = temp[temp.size() - 1] - 'a';

    outdegree[first]++;
    indegree[last]++;
    graph[first][last]++;
  }
  if (isConnected(indegree, outdegree, graph)) {
    cout << "Ordering is possible.\n";
  } else {
    cout << "The door cannot be opened.\n";
  }
}

int main(int argc, char *argv[]) {
  int t;
  cin >> t;
  while (t-- > 0) {
    solve();
  }
  return 0;
}