11403번 - 경로찾기

문제 요약

1. 입력값으로 그래프를 나타내는 인접행렬이 들어온다.
2. 그래프의 노드 s에서 출발하여 노드 e에 갈수 있는지 여부를 n x n 행렬로 출력해야한다.(1 <= s, e <= n)

접근법

이 문제는 그래프를 BFS 탐색하는 문제이다. 이 문제역시 어려운 문제는 아니라고 생각된다. 이 문제를 풀기위해서 노드 s에서 출발하여 갈수 있는 모든 노드 e를 구한뒤 따로 2차원 배열로 만듦으로써 문제를 해결할 수 있었다.

예제 입력으로 다음과 같은 입력이 주어졌다.
|Node|Node|Node|
|—|—|—|
| 0| 1| 0|
| 0| 0| 1|
| 1| 0| 0|

위의 예제 입력을 그래프로 그려보면 다음과 같다.

노드 1에서 출발한다고 했을 때, 노드 1은 노드 2로 갈 수 있다. 또한 노드 1은 노드 2를 거쳐 노드 3도 갈 수 있다. 마지막으로 노드 1은 노드 2, 노드 3을 거쳐 자기 자신으로 돌아올 수 있다.

노드 2에서 출발한다고 했을 때, 노드 2는 노드 3으로 갈 수 있다. 또한 노드 2는 노드 3을 거쳐 노드 1로 갈 수 있다. 마지막으로 노드 2는 노드 3, 노드 1을 거쳐 자기 자신으로 돌아올 수 있다.

노드 3에서 출발한다고 했을 때, 노드 3은 노드 1로 갈 수 있다. 또한 노드 3은 노드 1을 거쳐 노드 2로 갈 수 있다. 마지막으로 노드 3은 노드 1, 노드 2를 거쳐 자기 자신으로 돌아올 수 있다.

위와 같이 1부터 n까지의 노드에서 출발했을 때 도착할 수 있는 노드들을 BFS를 이용하여 계산하고 이를 2차원 배열의 형태로 출력하면 쉽게 문제를 해결할 수 있다. 다만 위와 같은 알고리즘을 사용하면 중복해서 계산하는 부분이 생기기 때문에 조금 더 실행시간을 단축시킬 수 있는 좋은 방법이 있을 것이라고 생각한다. (모든 노드에 대해 계산하는 것이 아니라 모든 노드들의 path를 한번에 구할 수 있는 방법등)

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)