[파이썬] 백준 11403 : 경로 찾기 (실버1)

[파이썬] 백준 11403 : 경로 찾기 (실버1)

---

문제

---

풀이

0.방향성 생각

방향성 있는 그래프. 입력을 받아서 각 노드에서 몇 번 노드로 갈 수 있는지 arr에 추가해준다.

인접행렬로 표현하라 했으므로 2차원 배열 visit을 만들어주고 BFS로 체크

 

1. 입력받기, 경로 추가

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
arr = [[] for i in range(n)]
for i in range(n):
    temp = list(map(int,input().split()))
    for j in range(n):
        if temp[j] == 1:
            arr[i].append(j)

 

2. BFS 탐색

visit = [[0]*n for i in range(n)]

for i in range(n):
    q = deque()
    for j in arr[i]:
        q.append(j)
    while q :
        x = q.popleft()
        visit[i][x] = 1
        for k in arr[x] :
            if not visit[i][k] :
                q.append(k)
    print(*visit[i])

각 노드 번호에서 시작해서 BFS를 실행.

출발점에서는 방문 체크를 하지 않는다. 시작점에서 시작해서 다시 올 수 있는지 모른다.

방문하지 않은 곳을 갔을 경우에는 큐에 추가

---

전체코드

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
arr = [[] for i in range(n)]
for i in range(n):
    temp = list(map(int,input().split()))
    for j in range(n):
        if temp[j] == 1:
            arr[i].append(j)

visit = [[0]*n for i in range(n)]

for i in range(n):
    q = deque()
    for j in arr[i]:
        q.append(j)
    while q :
        x = q.popleft()
        visit[i][x] = 1
        for k in arr[x] :
            if not visit[i][k] :
                q.append(k)
    print(*visit[i])

 

코멘트

시간제한이 빡센 문제는 아니라서 간단한 BFS 형태로 풀었다.

중복 탐색을 줄이기 위한 리스트가 있으면 더 효율적으로 풀었을듯.