백준 11403번 경로 찾기 자바 문제 풀이

백준 11403번 경로 찾기 자바 문제풀이

문제에서 가중치 없는 방향 그래프가 주어집니다. 가중치가 없다. 방향이 있다는 것만 캐치하면 될 것 같습니다.

플로이드 와샬로 푸는 방법도 있는 것 같습니다만 아직 해당 알고리즘에 익숙치 않아서 DFS 방식으로 접근했습니다.

N 범위는 100까지기 때문에 N2 탐색을 하더라도 시간 문제는 없어보였습니다.

 

 

 

백준 11403번 경로 찾기 그림 풀이

위와 같은 형태 즉, arrayList를 선언해서 node를 만들고 각각의 방향 그래프를 탐색해나가는 형태로 풀었습니다. 문제에서 특정 노드가 다른 노드로 향하는 방향이 주어지기 때문에 그걸 참고해서 graph를 만들었고, 각 node들을 돌면서 방문이 가능한 node들을 표시해나갔습니다.

진행 순서를 보면 이처럼 볼 수 있습니다. 0번 노드로 시작한다면 0번 노드가 갈 수 있는 방향을 탐색합니다. 그리고 그 노드에 또 다른 노드로 향할 수 있는 길이 있다면 이어서 진행합니다. 한번 방문한 노드는 visited 배열에 표기해줍니다. 한 번 이상 방문한 노드는 어차피 같은 길을 가는것이기 때문에 visited가 true로 되어있는 칸은 더 이상 진행하지 않아주면서 0번 노드에서 갈 수 있는 노드가 어떤것인지를 visited 배열로 확인할 수 있게됩니다.

 

 

테스트 케이스

입력
4
0 1 1 0
0 0 0 1
0 0 0 0
1 0 0 0

출력
1 1 1 1
1 1 1 1
0 0 0 0
1 1 1 1

입력
4
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0

출력
0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0