프로그래머스 알고리즘 - 단어변환 ☞ 단어변환 문제 링크 문제의 핵심은 각 word를 노드로 두고, 변환 가능한 word간에는 간선(edge)로 연결해둔 다음에 그래프 탐색을 진행하면 어렵지 않은 문제 였습니다.☞ 그래프(Graph) DFS 탐색 구현하기 문제풀이 코드의 전체적인 틀은 그래프 탐색을 응용합니다. class Graph { private Word[] words; . . . } 입력값의 문자를 이용한 만든 클래스 Word를 그래프 탐색의 노드(Node)로 치환합니다. class Word { private String name; private List changeable; //인접 노드(Word)들을 저장하는 리스트 private boolean visited; . . . } 주어진 word와 기..
프로그래머스 알고리즘 - 네트워크 ☞ 네트워크 문제 링크 그래프 탐색을 코드로 구현 할 줄 알아야 풀 수 있는 문제였습니다. ☞ 그래프(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)와 BFS, DFS
그래프(Graph) 그래프란 여러 객체들과 그 객체들 간의 연결된 관계를 표현하는 방법 입니다. 친숙한 예제로 지하철 노선도를 생각해보시면 됩니다. 여러 지하철역들과 그 역들 간의 연결된 관계를 표시 해줍니다. 그래프에서 각 객체ㅁ들을 정점(vertex) 혹은 노드(node)라고 많이 부르고, 이들을 연결하는 선들을 간선(edge-엣지) 라고 부릅니다.이미지 출처 : https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/ BFS(Breadth First Search)그래프의 모든 노드들을 한번 씩 탐색하기 위한 방법 중에 하나입니다. 말그대로 너비(Breadth)를 우선(First)으로 탐색(Search)하는 방법입니다. 시작점이 되는 노드..