[알고리즘] BOJ 11403번 - 경로 찾기(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

2 / 50

 

탐색

2 / 50(NEW!)

 

기초 동적 프로그래밍

2 / 50

 

투포인터

0 / 10

---

문제

11403번: 경로 찾기 (acmicpc.net)

11403번: 경로 찾기

→ solved.ac 기준 실버 1 문제

→ class 3++

---

문제 해결 아이디어

가중치 없는 방향 그래프 G에 대해서 경로 파악하는 문제 → 그래프 탐색

⇒"모든" 정점 (i, j)에 대한 경로가 있는지를 구해야 한다는 게 핵심으로 보인다.

그래프 탐색 알고리즘 중 모든 노드엣어 다른 모든 노드의 최단 경로를 계산하는 플로이드위셜 알고리즘을 사용

시간 복잡도는 O(N^3)이지만, 정점의 개수가 최대 100이므로 가능

---

구현

내 풀이

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

# 플로이드 위셜 알고리즘 수행
for k in range(n): # k - 거쳐가는 노드
  for a in range(n): # a - 출발 노드
    for b in range(n): # b - 도착 노드
      if (graph[a][b] == 1) :
        continue
      elif (graph[a][k] == 1 and graph[k][b] == 1) :
        graph[a][b] = 1

# 수행 결과 출력
for i in range(n):
  for j in range(n):
    print(graph[i][j], end=' ')
  print()

 

다른 사람 풀이

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

# 플로이드 위셜 알고리즘 수행
for k in range(n): # k - 거쳐가는 노드
  for a in range(n): # a - 출발 노드
    for b in range(n): # b - 도착 노드
      if graph[a][k] and graph[i][k]:
        graph[a][b] = 1

# 수행 결과 출력
for g in graph:
	print(*g)

플로이드 위셜 알고리즘 수행 시 if 문 사용이 훨씬 깔끔함

python에서 1과 0이 True False인 걸 이용해서 and문으로 구현

출력 시 *을 사용

 

혹은 플로이드 위셜 알고리즘이 아닌 dfs와 bfs를 사용해서 푸는 방법도 존재

---

메모

• 걸린 시간: 30분

---