[백준BOJ] 11403번 경로 찾기.py

 

백준 저지에서 경로 찾기를 파이썬을 통해 풀어 보았다. 

 

11403번 경로 찾기.py

tomy9729/Algorithm

 

 

11403번 경로 찾기

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오

설명

그래프, 정점, 경로 이 세 단어만 봐도 BFS 또는 DFS로 풀 수 있는 문제라는 것을 알 수 있다. 

 

주어진 행렬을 통해 단방향 그래프를 만들고 이에 대해 BFS 또는 DFS를 구현하여 경로가 있는지 확인하면 된다. 경로가 있다면 1을 반환하고 1을 반환하지 못하고 BFS를 전부 돌았다면 0을 반환한다.

 

단 특이점이 하나 있다. i와 j가 같은 경우이다. 처음에는 i와 j가 같다면 그대로 가만히 있어도 도착한 것이니 경로가 있는 것으로 구현했다. 그러나 문제에서 말하는 경로는 노드를 최소 하나 이상 이동했을 때이다. 즉 다른 노드를 거쳐 다시 자기 자신으로 돌아왔을 때 경로가 있는 것이 된다.

 

다시 자기 자신으로 돌아오게 하기 위해서 처음 출발점 i에 대해 방문하지 않은 것으로 해야한다. 그래야만 다시 자기 자신으로 돌아올 수 있기 때문이다.

코드

#11403번 경로 찾기
def BFS(graph,i,j,visit) : 
  q = [i]
  while q :
    now = q.pop(0)
    for next in graph[now] : 
      if visit[next] == False : 
        visit[next] = True
        if next == j : 
          return 1
        q.append(next)
  return 0


if __name__ == "__main__":
  n = int(input())
  graph = [[] for _ in range(n)]
  for i in range(n) :
    g = list(map(int,input().split()))
    for j in range(n) : 
      if g[j] == 1 :
        graph[i].append(j)
  visit = [False]*n
  for i in range(n) :
    for j in range(n) : 
      visit = [False]*n
      print(BFS(graph,i,j,visit),end=" ")
    print()