프로그래머스 알고리즘 - 네트워크 ☞ 네트워크 문제 링크 그래프 탐색을 코드로 구현 할 줄 알아야 풀 수 있는 문제였습니다. ☞ 그래프(Graph) DFS 탐색 구현하기 문제풀이코드의 전체적인 틀은 그래프 탐색을 응용합니다.네트워크망은 그래프로 치환하고, 각각의 컴퓨터를 노드로 치환합니다.class Network { class Computer { . . . } . . . } 탐색한 컴퓨터가 어떤 컴퓨터에도 연결되어 있지 않다면 네트워크의 숫자를 하나 증가시킵니다. class Network{ . . . void isNewNetwork(Computer computer) { if(!computer.connected) network++; } } 모든 컴퓨터를 탐색하기 위해서, 탐색은 모든 컴퓨터를 기점으로 시작..
그래프와 BFS DFS의 개념, 그래프 구현방법은 이전 포스팅을 참고 ☞그래프(Graph)와 BFS, DFS☞그래프(Graph) 인접 리스트(adjacency list)로 구현하기그래프 생성하기 먼저 그래프를 생성하고 아래 그림과 같은 관계를 갖는 노드들을 만들겠습니다. (그래프와 구현은 이전 포스팅에 있습니다 ☞그래프(Graph) 인접 리스트(adjacency list)로 구현하기.) public class DFSBFS { public static void main(String[] args) { Graph graph = new Graph(5); graph.setNode(); graph.addEdge(0, 1); graph.addEdge(0, 4); graph.addEdge(1, 0); graph.add..
그래프(Graph) 인접 리스트(adjacency list)로 구현하기
그래프와 DFS BFS에 대한 설명은 이전 포스팅을 참고 ☞ 그래프(Graph)와 BFS, DFS 그래프(Graph) 구현하기 그래프를 구현하는 방법은 크게 2가지가 있습니다. 인접 행렬(adjacency matrix)로 구현하는 방법과 인접 리스트(adjacency list)로 구현하는 방법이 있습니다. (간선(edge)이 많은 경우 인접 행렬(adjecency matrix)로 구현하는 것이 좋고, 아닌 경우 인접리스트로 구현하는 것이 유리하다 라고 알고 있습니다만 간선이 '많다'의 기준을 저는 잘 모르겠습니다. 공부해야 할 영역입니다.) 이 포스팅에서는 인접 리스트로 구현해 보도록 하겠습니다. 인접 리스트(adjacency list)로 그래프 구현하기 노드(정점)들의 연결 관계를 어떤 식으로 저장해 ..
그래프(Graph)와 BFS, DFS
그래프(Graph) 그래프란 여러 객체들과 그 객체들 간의 연결된 관계를 표현하는 방법 입니다. 친숙한 예제로 지하철 노선도를 생각해보시면 됩니다. 여러 지하철역들과 그 역들 간의 연결된 관계를 표시 해줍니다. 그래프에서 각 객체ㅁ들을 정점(vertex) 혹은 노드(node)라고 많이 부르고, 이들을 연결하는 선들을 간선(edge-엣지) 라고 부릅니다.이미지 출처 : https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/ BFS(Breadth First Search)그래프의 모든 노드들을 한번 씩 탐색하기 위한 방법 중에 하나입니다. 말그대로 너비(Breadth)를 우선(First)으로 탐색(Search)하는 방법입니다. 시작점이 되는 노드..