[Algorithm] 깊이 우선 탐색 (Depth First Search)

15723번 - n단 논법

1. 문제

• 모든 중앙대 컴퓨터공학부(소프트웨어학부) 학생들은 미인이다.
• 지무근은 중앙대 컴퓨터공학부 학생이다.
• 그러므로 지무근은 미인이다.

위 연역 논증은 대표적인 삼단논법의 예시이다. 삼단논법이란 전제 두 개와 결론 하나로 이루어진 연역 논증이다. 이것을 응용하면, $n$ 개의 전제가 있을 때 $m$ 개의 결론을 도출할 수 있을 것이다. 이때의 $n$과 $m$은 모든 의미에서 적절한 수라고 가정하자. 자세한 것은 입출력 예시를 확인하자.

• Input

첫째 줄에 정수 $n(2 \le n \le 26)$ 이 주어진다.

둘째 줄부터 $n$개의 줄에 걸쳐 각 줄에 전제가 하나씩 주어진다. 전제는 모두 a is b의 형식으로 주어지며 a와 b는 서로 다른 임의의 알파벳 소문자이다. 특별한 명시는 없지만 모든 전제는 "모든 a는 b이다"라는 의미이다. 하지만 "모든 b는 a이다"의 의미는 될 수 없다. 또한 a는 b이면서 c일 수 없으나, a와 b가 동시에 c일 수는 있다.

$n + 2$ 번째 줄에 정수 $m(1 \le m \le 10)$ 이 주어진다. 그 다음 $m$개의 줄에 걸쳐 각 줄에 하나의 결론이 전제와 같은 형식으로 주어진다.

• Output

$m$ 개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F 를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다.

2. 사용 알고리즘

• 깊이 우선 탐색 (DFS)

3. 풀이

3.1. 조건 명제

a is b 라는 명제는 수학적으로 다음과 같이 표현한다.

$$a \rightarrow b$$

예시)

• 사람($a$)은 죽는다($b$).

문제에서 제시된 삼단 논법은 다음과 같은 형태이다.

대전제: $b \rightarrow c$
소전제: $a \rightarrow b$
결론: $a \rightarrow c$

예시)

• 대전제: 모든 인간($b$)은 죽는다($c$).
• 소전제: 소크라테스($a$)는 인간이다($b$).
• 결론: 소크라테스($a$)는 죽는다($c$).

이를 이어서 표현하면 다음과 같다.

$$a \rightarrow b \rightarrow c$$

이는 방향 그래프 형태로 나타낼 수 있다.

또한 어떤 명제가 참일 때 그로 인해 참이 될 수 있는 다른 명제가 2개 이상 존재하지 않는다고 문제에 명시되어 있다.

즉,

$$(a \rightarrow b) \land (a \rightarrow c)$$

가 참이되기 위해서는

$$(b \rightarrow c) \land (c \rightarrow b)$$

역시 참이어야 한다는 것을 의미한다.

예시)

• 모든 인간($a$)은 죽는다($b$).
• 모든 인간($a$)은 생각한다($c$).

예시에서 죽는 것($b$) 과 생각하는 것($c$) 사이에는 논리적 종속 관계가 없으므로 $a \rightarrow b$ 가 주어졌다면, $a \rightarrow c$ 는 입력으로 주어지지 않는다는 뜻이다.

하지만 서로 다른 두 명제 $a$ 와 $b$ 가 동일한 결론 $c$ 를 공유할 수 있는 경우, 그 둘 사이에 논리적 종속 관계가 존재하지 않더라도 입력으로 주어질 수 있음을 암시한다.

$$a \rightarrow c \\ b \rightarrow c$$

예시)

• 모든 남자($a$)는 죽는다($c$).
• 모든 여자($b$)는 죽는다($c$).

즉, 위와 같은 예시는 가능하다.

3.2. 그래프

문제 해결을 위해 사용될 그래프 특성을 정리하면 다음과 같다.

1. 방향 그래프이다.
2. 그래프의 임의의 두 간선 $E_1 (t_1, h_1)$, $E_2 (t_2, h_2)$ 에 대하여
   2.1. $t_1 \ne t_2$ 를 만족한다.
   2.2. $h_1 = h_2$ 인 두 간선이 존재할 수 있다.
3. 사이클이 존재할 수 있다.

3.3. 알고리즘

임의의 결론 $x \rightarrow y$ 의 참⋅거짓을 판별하기 위해서는 그래프의 $x$ 노드를 시작으로 그래프 탐색을 수행하여야 한다. 이때, 일련의 노드에서 $y$ 노드가 존재하면 참, 그렇지 않으면 거짓 이라고 할 수 있다.

하지만 어떤 노드에 대해 도착 노드는 항상 하나만 존재하므로 탐색은 선형적으로 이루어진다. 다만, 사이클은 존재할 수 있으므로 불필요하게 재탐색된 노드에 대해 종료조건을 부여하여야 한다.

4. 구현

이제 실제로 구현해보자.

4.1. 값 입력

전제와 결론을 입력받아 각각 premises 와 conclusions 리스트 변수에 할당한다.

premises = [input().split(' is ') for _ in range(int(input()))]
conclusions = [input().split(' is ') for _ in range(int(input()))]

4.2. 그래프 초기화

입력된 전제목록을 통해 그래프를 초기화시킨다.

graph, visited = {}, []
for p1, p2 in premises: graph[p1] = p2

4.3. 탐색 함수 search() 구현

재귀함수를 이용한 깊이 우선 탐색(DFS) 알고리즘을 구성하였다. 다만 탐색이 선형적으로 이루어진다.

def search(node, find):
  if node == find: return 'T'
  if node not in graph or node in visited: return 'F'
  visited.append(node)
  return search(graph[node], find)

1. 현재 노드가 찾고자 하는 노드일 경우 참 을 반환한다.
2. 더 이상 탐색을 진행할 수 없거나, 이미 방문한 노드일 경우 거짓 을 반환한다.
3. 다음 노드를 탐색한다.

4.4. 출력

참⋅거짓을 판별할 결론들을 탐색 함수 search() 를 통해 탐색하고 결과를 출력한다.

for c1, c2 in conclusions: 
  visited.clear()
  print(search(c1, c2))

5. 제출 코드

맞았습니다!!

premises = [input().split(' is ') for _ in range(int(input()))]
conclusions = [input().split(' is ') for _ in range(int(input()))]

graph, visited = {}, []
for p1, p2 in premises: graph[p1] = p2

def search(node, find):
  if node == find: return 'T'
  if node not in graph or node in visited: return 'F'
  visited.append(node)
  return search(graph[node], find)

for c1, c2 in conclusions: 
  visited.clear()
  print(search(c1, c2))

6. 반례모음

다음으로 풀이에 도움이 될만한 반례를 기술한다.

반례1

출력 오류 (a is a 꼴)

• 입력

1
a is b
1
a is a

• 정답

T

반례2

시간 초과 (사이클 미확인)

• 입력

3
c is b
a is b
b is c
3
b is a
a is c
c is a

• 정답

F
T
F

반례3

시간 초과 (사이클 미확인)

• 입력

4
a is b
b is c
c is d
d is b
5
a is c
a is d
d is c
b is d
d is a

• 정답

T
T
T
T
F

---

관련 포스팅

• [Algorithm] 깊이 우선 탐색 (Depth First Search)