[백준] 11403번 경로 찾기 파이썬 해설 (Python)

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

11403번: 경로 찾기

BFS와 DFS 혹은 플로이드 와샬 알고리즘으로 분류된 문제이다.

BFS : Breadth-first search
DFS : Depth-first search

플로이드 와샬 알고리즘은 시간 복잡도가 O(n^3)이기 때문에 위 두 가지 방법으로 푸는 것을 추천한다.

 

풀이

---

이전에 BFS 혹은 DFS알고리즘 문제를 푼적이 있다면,
해당 문제에서 사요한 코드를 조금만 변형하면 풀 수 있는 문제이다.

문제를 풀기위해 알고리즘을 설계했던 순서는 다음과 같다.
1. 그래프에 대한 정보를 입력받아 N x N의 크기를 같은 배열을 만든다.
2. 한 개의 정점에 대해서 BFS를 수행한다.
3. BFS를 진행하면서 방문한 노드를 체크한다.
4. 방문한 노드에 관한 정보를 그대로 출력한다.
5. N개의 정점에 대해 반복적으로 2 ~ 4 과정을 수행한다.

주의할 점이 한 가지있다.
자기 자신으로 가는 경로를 처리하는 과정에서 헷갈릴 수가 있다.
자기 자신으로 돌아오는(ex - 1에서 1로 가는) 직접적인 경로는 없다고 문제에 쓰여있다.
따라서 다른 노드를 통해서만 자기 자신에게 도착할 수 있고 이 또한 방문한 노드에 관한 정보를 담는 배열에 담긴다.

 

정답 코드

import sys
input=sys.stdin.readline

def BFS(i, arr, n):
    visit=[0] * n
    q=[i]

    while q:
        index=q.pop(0)
        for i, v in enumerate(arr[index]):
            if visit[i] == 0 and v == 1:
                visit[i] = 1
                q.append(i)

    return visit

if __name__ == "__main__":
    n = int(input())
    arr = []
    for _ in range(n):
        arr.append([*map(int,input().split())])
    for i in range(n):
        print(' '.join(map(str,BFS(i,arr,n))))

 

결과 인증

---

오늘은 한 번만에 맞추긴 했는데 한 번만에 풀지 못했다..

그 이유는..

문제를 빠르게 풀고 흥분한 나머지 출력 형식을 맞추지 않고 제출해버렸다..

실수 또한 실력이니 앞으로 실전에선 이런 일이 생기지 않도록 조심해야겠다..