알고리즘/문제
[플로이드 워셜] 백준 2224 명제 증명
_Min
2021. 2. 27. 21:44
문제링크 www.acmicpc.net/problem/2224
[답코드]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (52) for _ in range(52)]
for _ in range(int(input())):
a, b, c = input().split()
a_ord = ord(a)
c_ord = ord(c)
# 소문자
if a_ord >= ord('a'):
a_ord = a_ord - (ord('a') - ord('Z') - 1)
# 소문자
if c_ord >= ord('a'):
c_ord = c_ord - (ord('a') - ord('Z') - 1)
a_ord = a_ord - ord('A')
c_ord = c_ord - ord('A')
graph[a_ord][c_ord] = 1
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(52):
for b in range(52):
if a == b:
graph[a][b] = 0
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(52):
for a in range(52):
for b in range(52):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
arr = []
# 수행된 결과를 출력
for a in range(52):
for b in range(52):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if graph[a][b] == 0 or graph[a][b] == 1e9:
pass
# 도달할 수 있는 경우 거리를 출력
else:
arr.append(a)
arr.append(b)
# print(graph[a][b], end=" ")
print(len(arr) // 2)
for i in range(0, len(arr), 2):
# print(arr[i], arr[i+1])
a = arr[i]
c = arr[i + 1]
# 소문자
if a > 25:
a = a + (ord('a') - ord('Z') - 1)
# 소문자
if c > 25:
c = c + (ord('a') - ord('Z') - 1)
a = a + ord('A')
c = c + ord('A')
print("%c => %c" % (chr(a), chr(c)))
|
cs |
[풀이법]
아스키코드를 이용해서 대문자는 인덱스 0~25까지 담고 소문자는 인덱스 26~51까지 담는다
728x90