[Baekjoon][Python] 11403번 경로 찾기

11403번 경로 찾기

문제

풀이

생각보다 간단한 문제이다.
DFS를 이용하면 쉽게 풀 수 있다.

하지만 인접행렬 그대로 풀 수도 있고, 인접 연결 리스트로 바꾸어 해결할 수도 있다. 두 풀이 모두 적어보겠다.

1. 입력 그대로 인접행렬로 풀 경우

   import sys
   input = sys.stdin.readline
   
   def existsPath(i, arr, answer, visited, origin):
       for p in range(N):
           if arr[i][p] == 1:
               if p not in visited:
                   visited.add(p)
                   answer[origin][p] = 1
                   existsPath(p, arr, answer, visited, origin)
       return visited
   N = int(input())
   
   arr = []
   answer = []
   
   for _ in range(N):
       arr.append(list(map(int, input().split())))
       answer.append([0] * N)
   
   for i in range(N):
       visited = set()
       existsPath(i, arr, answer, visited, i)
       for a in answer[i]:
           print(a, end=' ')
       print()
   

   

2. 인접 연결리스트로 바꾸어 풀 경우

   import sys
   input = sys.stdin.readline
   
   def existsPath(i, graph, answer, visited, origin):
       for p in graph[i]:
           if p not in visited:
               visited.add(p)
               answer[origin][p] = 1
               existsPath(p, graph, answer, visited, origin)
       return visited
   N = int(input())
   
   graph = []
   answer = []
   
   for i in range(N):
       graph.append([])
       tempList = list(map(int, input().split()))
       for j in range(N):
           if tempList[j] == 1:
               graph[i].append(j)
       answer.append([0] * N)
   
   for i in range(N):
       visited = set()
       existsPath(i, graph, answer, visited, i)
       for a in answer[i]:
           print(a, end=' ')
       print()
   

   

결론

결론적으로 보자면 인접 연결리스트로 푸는 것이 더 효율적이라고 할 수 있을 것 같다. 시간이 크게 단축 되었기 때문이다. 아마도 인접행렬의 경우 N만큼 반복문을 재귀를 하면서 돌지만, 연결리스트의 경우 연결된 노드 개수만큼만 돌기 때문에 훨씬 빠른 것으로 보인다.