인접행렬1 [알고리즘] 7-11 경로 탐색 - 인접행렬, 인접리스트, 깊이우선탐색(DFS) (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 문제 입력 설명 : 첫째 줄에는 정점의 수 n과 간선의 수 m이 주어지고 다음 줄부터는 m 줄에 걸쳐 연결 정보가 주어진다. 인접행렬과 인접리스트 두 가지 방법으로 풀이한다. 정점의 개수가 많은 경우 인접행렬을 사용하면 그만큼의 2차원 배열을 만들어야 하기 때문에, 정점의 개수가 1000개, 10000개와 같이 많을 때는 인접리스트를 사용하는 것이 좋다. 그래프 이론에서 경로는 한번 방문한 노드를 다시 방문하지 않는다. 그래서 checked 배열을 통해 노드 방문 여부를 체크한다. 풀이1 - .. 2021. 6. 17. 이전 1 다음