DFS27 [ 자바스크립트(JavaScript) ] 프로그래머스 level3 - 네트워크 📍 프로그래머스 3단계 - 네트워크 프로그래머스 3단계 - 네트워크 이 문제를 그래프의 개념을 알고 있어야 풀 수 있는 문제이기 때문에 조금 까다로울 수 있다. 결론적으로 visited 배열을 선언하여 노드 방문 여부를 체크해주면 된다. 4번째 줄에 반복문을 사용한 이유는 모든 노드를 한 번씩 탐색하기 위함이다. 만약, 모든 노드가 서로 연결되어있지 않다면 갈 수 없기 때문이다. 이때, 이전에 방문한 노드는 탐색하지 않도록 조건문을 넣어줬다. DFS 함수에서는 node와 연결된 다른 node를 방문하는 로직인데, 현재 노드에서 visited배열로 방문 체크해주고, 다음 노드와 연결되어있다면(computers[node][i]) 해당 노드로 이동하는데 이때 주의할 점은 방문하지 않은 노드여야 한다는 점이다... 2022. 3. 23. [ 자바스크립트(JavaScript) ] section09 - 6 - 섬나라아일랜드(DFS, BFS) 📍 section09 - 6 - 섬나라 아일랜드(BFS, DFS) 문제: N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 이 문제는 DFS 와 BFS탐색으로 모두 풀 수 있는 문제다. 이 방법을 이용하면 백준4963 - 섬의 개수도 한번 풀어보자! 먼저, DFS로 푸는 방법을 알아보자. visited 배열을 선언하지 않고 현재 좌표를 0으로 만든 다음에 대각선 좌표의 값이 1인 곳만 탐색한다.(이때, 재귀적으로 dfs 함수를 호출한다.) board를 돌면서 현재 좌표와 대각선 좌표까지 0이면 더 이상 탐색할 수 없으므로 다음 좌표로 넘어간다... 2021. 10. 12. [ 자바스크립트(JavaScript) ] section09 - 3 - 경로 탐색(인접리스트) 📍 section09 - 3 - 경로 탐색(인접리스트) 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하는 문제다. 예를 들어 1번 정점에서 5번 정점으로 가는 가지 수는 다음과 같다. 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 이전과 동일한 문제지만 이번에는 인접 리스트를 활용해서 푸는 문제다. 만약에 그래프를 이용한 문제에서 정점의 개수가 10,000개 이상이라면 인접리스트를 사용하자.(인접 행렬은 정점의 개수만큼 반복문을 돌아야 하기 때문에 비효율적이다.) 이 문제도 마찬가지로 DFS를 이용해서 풀 수 있다. 경로의 가짓수만 출력하는 것이 아니라 올바르게 이동했는지 알기 위해 path 변수를 추가했다.. 2021. 10. 6. [ 자바스크립트(JavaScript) ] section09 - 2 - 경로 탐색(인접행렬) 📍 section09 - 2 - 경로 탐색(인접행렬) 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하는 문제다. 예를 들어 1번 정점에서 5번 정점으로 가는 가지 수는 다음과 같다. 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 이 문제는 DFS를 이용해서 풀 수 있다. 경로의 가짓수만 출력하는 것이 아니라 올바르게 이동했는지 알기 위해 path 변수를 추가했다. 2차원 배열의 graph를 선언하여 정점과 간선의 정보를 넣는다. visited 배열을 선언하여 이미 지나온 곳은 건너뛰고 진행한다. DFS의 종료 조건은 v가 n과 같을 때이다. 인접 행렬이므로 반복문으로 모든 정점을 탐색해야 한다. DFS 함수.. 2021. 10. 6. [ 자바스크립트(JavaScript) ] section09 - 1 - 그래프와 인접행렬 📍 section09 - 1 - 그래프와 인접행렬 이번 섹션은 그래프와 탐색(DFS, BFS)에 대해서 배운다. 지금은 문제를 풀지 않고 그래프에 대해 간단하게 알아보는 시간을 가져보자. 그래프는 다음과 같이 이루어진다. Vertex: 정점, 노드 Edge: 노드와 노드를 연결하는 간선 graph: 2차원 배열에서는 index가 정점(vertex) 번호다. 그래프의 종류는 3가지가 있다. 입력이 주어질 때 graph별로 어떻게 입력하는지 코드로 나타냈다. (여기서는 인접 행렬로 표현함) 1. 무방향 그래프(unDirected Graph): 방향이 없는 그래프 즉, 양방향인 그래프다. 입력은 보통 [a, b] 형태로 주어지는데 여기서 graph[a][b]=1, graph[b][a]=1을 모두 수행한다. /.. 2021. 10. 6. 이전 1 2 3 4 ··· 6 다음
