[BOJ] 자바의 형변환

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

BOJ - 자바의 형변환

문제 유형 : 해시, 그래프, 트리

문제 난이도 : Silver I

시간 제한: 2초

메모리 제한: 512MB

 

문제

자바의 클래스끼리는 상속을 통해 자신의 기능 일부를 다른 클래스에게 이식할 수 있다. 여기서 상속을 받은 클래스는 자식 클래스, 상속을 한 클래스는 부모 클래스가 된다. 클래스를 이용해서 만든 객체는 다른 클래스로 형태를 변환할 수 있는데, 이를 형변환(Casting)이라고 한다. 만약 자식 클래스에서 부모 클래스로 변환한다면 업캐스팅(Upcasting), 부모 클래스에서 자식 클래스로 변환한다면 다운캐스팅(Downcasting) 이라고 부른다. 즉, 자식 클래스와 부모 클래스 관계에 놓여있다면 형변환이 가능하다. Downcasting의 경우 런타임에 문제를 발생시킬 수 있지만 이는 본 문제에서 고려하지 않는다. 또한, 자바에서는 클래스의 다중 상속은 지원하지 않는다

예를 들자면, number 클래스는 object 클래스를 상속받는다. 따라서, number 클래스는 object 클래스의 자식 클래스가 되고, object 클래스는 number 클래스의 부모 클래스가 된다.

또한, 자식 클래스가 여러 단계를 거쳐 상속을 받은 경우, 이 자식 클래스에게 상속을 해준 클래스들 모두 부모 클래스가 된다. 예를 들면, integer 클래스의 경우 number 클래스로 부터 상속을 받고, 이 number 클래스는 object 클래스의 상속을 받았으니, integer 클래스는 number, object 클래스로부터 상속을 받은 것과 같다. 따라서, integer 클래스와 object 클래스는 부모 - 자식 관계가 되기 때문에 두 클래스간 형변환이 가능하다.

입력으로 N개의 임의의 클래스들간의 관계를 입력받고, 검사할 두 클래스에 대한 정보가 주어진다. 만약, 서로 형변환이 가능하면 1, 아니면 0을 출력한다.

 

입력

첫 줄에 클래스의 수 N이 주어진다. (2≤N≤100 000)

다음 N−1개의 줄에 각 클래스 간의 관계 정보가 주어진다. A, B가 순서대로 주어지며 이는 A가 B의 자식 클래스란 뜻이다. A, B는 알파벳 소문자로 구성된 길이 2 이상 50 이하의 문자열이다.

마지막 줄엔 서로 형변환이 가능한지 확인할 두 클래스가 주어진다. 항상 N−1개 줄의 입력에서 주어졌던 클래스만 나오며, 두 클래스의 이름은 서로 다르다.

입력을 통해 만들어지는 트리는 하나의 루트가 있는 트리이다.

 

출력

두 클래스가 형변환이 가능하면 1, 아니라면 0을 출력한다.

 

풀이

해시맵으로 트리를 만들면 된다.

mp[자식클래스명] = 부모클래스명으로 관계를 맺으면 된다.

 

그리고 마지막으로 받은 두 클래스를 각각 classA, classB라 했을 때,

classA부터 루트까지 가면서 classB를 만나면 1을 출력하고 그만두면 된고,

classB부터 루트까지 가면서 classA를 만나면 1을 출력하고 그만두면 된다.

둘 다 무사히 마치면, 0을 반환한다.

 

classA와 classB는 조상-후손의 관계여야 한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n;
  cin >> n;

  unordered_map<string, string> mp;

  for (int i = 0; i < n - 1; ++i) {
    string A, B;
    cin >> A >> B;

    mp[A] = B;
  }
  string classA, classB;
  cin >> classA >> classB;
  string curr = classA;
  while (mp[curr] != "") {
    if (mp[curr] == classB) {
      cout << "1\n";
      return 0;
    }
    curr = mp[curr];
  }

  curr = classB;
  while (mp[curr] != "") {
    if (mp[curr] == classA) {
      cout << "1\n";
      return 0;
    }
    curr = mp[curr];
  }

  cout << "0\n";

  return 0;
}