BFS4 [Java] 자료구조 - 그래프 [Java] 자료구조 - 그래프 그래프란? 정점 (Vertex, Node)와 간선 (Edge)로 이루어져 있다 트리, 이진트리도 그래프의 한 종류인다 그래프는 무방향 그래프와, 방향 그래프가 있다 무방향 그래프는 정점과 정점 사이에 방향이 없는 그래프이다 (즉 모든 정점들은 서로 왕복을 할 수 있다) 방향 그래프 같은 경우 정점에서 어느 정점으로 갈 수 있는 방향이 정해져 있다 (방향이 정해져 있으면, 그 방향 밖에 갈 수 없다) 정점 (Vertex) : 노드(Node)라고도 하고, 값 또는 데이터를 저장한다 간선 (Edge) : 정점을 연결하는 선이다 분지수 (차수, degree) : 무방향 그래프에서 하나의 정점과 연결되어 있는 간선의 수 내향 분지수 (진출 차수, in-degree) : 방향 그래프.. 2023. 6. 26. [Python] 백준 1389 케빈 베이컨의 6단계 법칙 🧑💻 [Python] 백준 1389 케빈 베이컨의 6단계 법칙 Silver 1 - BFS BFS 를 사용하면서 풀었다 각 숫자, 즉 1부터 N까지의 숫자와 친구의 거리를 모두 구해야 한다 for i in range(1, N + 1) 과 for j in range(1, N + 1)인 2중 for문을 통해서 각 친구들 간의 거리를 구한다 코드 from collections import deque def bfs(start, end, link_num): queue = deque() queue.append((start, 0)) visited = [0] * link_num visited[start] = 1 while queue: current, score = queue.popleft() if current == .. 2023. 3. 29. Udemy : 알고리즘 DFS, BFS, 백트래킹 Udemy : 알고리즘 DFS, BFS, 백트래킹 udemy 알고리즘 코딩 테스트 그래프 자료구조 그래프는 노드와 링크로 이루어진 자료구조다 노드는 점들이고, 노드를 이어주는 링크, Edge 또는 간선이라고 한다 SNS / 메신저 관계도를 그래프로 만들 수 있다 지도 / 네비게이션 같이 그래프를 실생활에 사용될 수 있다 무방향 또는 방향 그래프로 만들 수 있다 무방향이나 양방향 그래프는 동일한 개념이다 트리 자료구조 순환성이 없는 무방향 그래프다 코드를 그래프로 나타날 때에는 인접 리스트와 행열을 만들 수 있다 연결 행 연결 리스트 DFS (Depth First Search) 깊이 우선 탐색 스택 또는 재귀를 사용해서 구현을 한다 DFS는 완전 탐색이다 BFS (Breadth First Search) 너.. 2023. 3. 13. [Python] 백준 7576 토마토 🧑💻 [Python] 백준 7576 토마토 Gold 5 - BFS 무조건 BFS로 풀어야 하는 문제이다 시작점이 하나가 아닐 수 있다 그래서 queue 안에다 시작점들을 모두 찾아서 넣는다 BFS를 할때마다 주변 노드에다 방문 표시 대신 1을 더해서, 더한 숫자를 넣는다 마지막에 다시 탐색을 해야하는데, 0이 하나라도 있으면 -1을 출력하고, 그게 아니면 더한 숫자들 중 제일 큰 숫자에 1을 빼서, 답을 출력한다 문제풀이 bfs 식 주변을 탐색하고, 주변에 있는 노드 위주로 탐색하기 위해 popleft를 사용 첫 for문 queue에다가 시작 점들을 넣는다 시작점이 하나일 때에는 for문을 돌릴 필요가 없지만, 이 문제에서는 시작점이 1개 이상이 주어질 수 있다 두번째 for문 결과값을 탐색한다 bfs.. 2023. 2. 13. 이전 1 다음
