[Python Algorithm] 경로 찾기 BOJ #11403 (feat. BFS, 플로이드 워셜)

문제

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

11403번: 경로 찾기

 

내 문제 풀이 (BFS)

import sys
sys.setrecursionlimit(10 ** 6)

n = int(sys.stdin.readline().strip())
table = []
for _ in range(n):
    table.append(list(map(int, sys.stdin.readline().strip().split())))
result = table

def bfs(queue, find, checkList):
    idx = 0
    check = False

    while idx < len(queue):
        now = queue[idx]
        idx += 1

        if 1 not in table[now]:
            continue
        else:
            for x in range(n):
                if table[now][x] == 1 and checkList[now][x] is False:
                    checkList[now][x] = True
                    if x == find:
                        check = True
                        break
                    else:
                        queue.append(x)
                if check:
                    break

        if check:
            break

    if check:
        return 1
    else:
        return 0

for i in range(n):
    for j in range(n):
        if result[i][j] == 1:
            continue
        else:
            checkList = [[False for _ in range(n)] for _ in range(n)]
            checkList[i][j] = True
            result[i][j] = bfs([i], j, checkList)

print('\n'.join(' '.join(map(str, i)) for i in result))

👉 BFS로 풀이 (플로이드 워셜 알고리즘을 몰라서 bfs로 풀이했다.)

• 행렬을 돌며 1이 있을 경우 경로가 확인된 것이므로 그대로 result에 1을 저장했다.
• 그 외의 경우에는 bfs 함수를 이용하여 경로를 확인해주었는데, 중복을 피하기 위한 checkList 함수도 생성했다.
  시작하는 자리만 True로 바꿔놓고 bfs 함수를 호출했다.
• bfs 함수에서는 queue에 탐색이 필요한 행들을 추가하며 확인해주었다.
  예를 들어 a, b 자리에 대한 결과를 가져오고자 할 때, queue에는 a가 저장되어 있을 것이다.
  그리고 b까지 도달하기 위해서는 중간에 어떠한 노드를 거치든지, 바로 가든지 한 선택지가 필요하다.
  따라서 가장 먼저 a행에 1이 저장된 곳이 있는지를 확인해준다.
  만약 1이 하나도 없다면 연결될 수 있는 가능성이 전혀 없다는 뜻이므로 continue 해준다.
  그렇지 않을 경우 1이 저장된 a행 모든 자리의 j 값을 queue에 추가하는데, (모두 가능성 있으므로)
  혹시 j 값이 처음에 찾고자 한 목적지인 b와 같다면 더이상 탐색할 필요가 없으므로 모두 종료한다.
  위와 같은 과정을 반복하여 연결 가능한 경로가 있는지 판별해줄 수 있다.

 

내 문제 풀이 (플로이드 워셜)

import sys
sys.setrecursionlimit(10 ** 6)

n = int(sys.stdin.readline().strip())
table = []
for _ in range(n):
    table.append(list(map(int, sys.stdin.readline().strip().split())))

for k in range(n):
    for i in range(n):
        for j in range(n):
            if table[i][k] and table[k][j]:
                table[i][j] = 1

print('\n'.join(' '.join(map(str, i)) for i in table))

👉 플로이드 워셜 알고리즘을 이용했다.

• k를 중간 노드로 생각하고, k값을 거치는 간선이 있는지를 확인했다.
• 3중 for문을 이용하여 모든 자리의 연결 가능성을 확인해줄 수 있었다.
  예를 들어 1 -> 3 -> 4 -> 5 로 연결되는 노드들이 있다고 가정하자.
  이 때 i == 1, j == 5 인 자리는 연결이 가능한 것을 알 수 있다.
  이를 플로이드 워셜 알고리즘에 적용하면,
  i행과 j열에서 각각 1이 존재하는지를 확인하고, 모두 존재한다면 연결이 가능한 것으로 판별한다.

+ 원래 플로이드 워셜 알고리즘은 a -> b 경로와 a -> c -> b 경로 중 더 가까운 것을 판별하고 업데이트해주는 역할을 하는데, 이 문제의 경우 거리를 판별할 필요없이 연결이 가능한지만 판단하면 되므로 위와같이 풀이하면 된다.

 

💡 피드백

• bfs로 풀이했을 때는 시간복잡도도 안좋았고 풀이도 복잡했는데
  플로이드 워셜 알고리즘을 활용하니까 훨씬 효율적으로 풀 수 있었다.