[Python] 15723번 n단 논법

✏️ 문제

 

문제 파악

다른 문제들과 달리 이 문제에서는 문자로 값을 주어 해당 문자에 해당하는 유니코드 정수를 반환하는 ord() 메소드를 사용해야 한다.

또한 a와 b의 값만 분리하기 위해 입력을 받을 때 split() 옵션을 잘 활용해야 한다. 

 

소문자 a 를 아스키코드 값으로 하면 97이므로 a를 0으로 기준을 잡으려면 -97 하면 된다.

u, v = map(str, input().split(' is '))
u = ord(u) - 97
v = ord(v) - 97
graph[u].append(v)

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색
• 최단 경로
• 플로이드-워셜

 

 

코드

from collections import deque

n = int(input())
graph = [[] * 28 for _ in range(28)]

for _ in range(n):
  u, v = map(str, input().split(' is '))
  u = ord(u) - 97
  v = ord(v) - 97
  graph[u].append(v)


def bfs(u, v):
  q = deque([u])
  visited = [0] * 28
  visited[u] = 1

  while q:
    node = q.popleft()

    if node == v:
      return 'T'

    for neighbor in graph[node]:
      if visited[neighbor] == 0:
        visited[neighbor] = visited[node] + 1
        q.append(neighbor)

  return 'F'

m = int(input())
for _ in range(m):
  u, v = map(str, input().split(' is '))
  u = ord(u) - 97
  v = ord(v) - 97

  print(bfs(u, v))

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS