# graph traversal
자료구조 정리9 : Graph
그래프 그래프는 노드나 노드들의 연결을 모은 것이다 앞에서 배운 트리는 그래프의 일종. 트리는 한 개의 노드(루트)에서 내려오는 여러 자식 노드의 형태. 그래프는 오늘날 매우 널리 쓰임. 모든 sns들이 그래프를 쓴다 영화추천 사이트, 쇼핑몰 넷플릭스나 아마존의 추천 알고리즘은 보통 데이터를 그래프 관계로 저장하는 것 ‘좋아하실 만한 상품’, ‘이런것도 있습니다’ Vertex - 노드를 가리키는 용어. 정점. Edge - 노드들 사이의 연결. 간선. Weighted/Unweighted(가중/비가중) 가중은 연결, 즉 간선 자체에 부여된 값이 있는 것이다. 지도 그래프에 도로의 길이가 간선마다 부여되어 있는 것이 그 예이다. Directed/Undirect
그래프 순회 (Graph Traversal)
그래프를 구성하는 모든 꼭짓점(Vertex)들을 체계적으로 방문하여 탐색하는 자료 검색 방법. 일반적으로 깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search) 두 종류가 많이 사용된다. (전위 운행법, 중위 운행법, 후위 운행법 등은 이 글에서는 생략한다.) DFS (Depth First Search) >한 노드를 시작으로 인접한 다른 노드를 탐색하기를 반복하여 끝까지 탐색하면 다시 상위 레벨의 다른 노드에서 탐색을 이어가며 모든 Vertex를 방문한다. '깊이 우선 탐색'이라는 말 그대로 깊은 곳으로 우선 탐색을 진행하는 방식. First In Last Out 방식의 Stack과 중복 처리를 방지하기 위해 이미 접근했던 Vertex를 저장하는 방식을 활용한다. [예시 1] 
[Python] 백준 1325 - 효율적인 해킹 문제 풀이
Overview BOJ 1325번 효율적인 해킹 Python 문제 풀이 분류: Graph Traversal (그래프 탐색), bfs 문제 페이지 풀이 코드 pypy3 채점 결과 통과하였다. bfs를 이용하여 해킹 가능한 컴퓨터 개수를 파악하여 답을 구한다. 그래프가 양방향이 아닌 단방향 이기 때문에 유니온 파인드를 사용할 수 없고, dfs를 이용하면 메모리 초과가 발생한다.
[Python] 백준 2636 - 치즈 문제 풀이
Overview BOJ 2636번 치즈 Python 문제 풀이 분류: Graph Traversal (그래프 탐색), bfs 문제 페이지 풀이 코드 1 - BFS 매 시간마다 좌표 (0, 0)에서부터 BFS 탐색을 통해 바깥 공기과 녹는 치즈를 확인한다. 탐색 과정에서 바깥 공기를 만나면 deque dq에 저장하고, 치즈를 만나면, 값을 0으로 바꾸고 cnt 변수에 1을 더한다. 그리고 탐색한 자리는 visit 값을 True로 변경하여, 중복되지 않게 한다. 이 과정을 치즈가 다 녹을 때까지 반복하여 답을 구한다. 풀이 코드 2 - 녹은 위치 저장 이전 풀이에서는 매번 좌표 (0, 0) 위치에서부터 bfs 탐색을 하기 때문에 이전에 이미 공기가 된 위치도 반복해서 탐색한다. 따라서 이번 풀이에서는 치즈가 녹아 새롭게 공기가 된 위치를 deque `
[Python] 백준 14502 - 연구소 문제 풀이
Overview BOJ 14502번 연구소 Python 문제 풀이 분류: Graph Traversal (그래프 탐색), dfs, bfs 문제 페이지 풀이 코드 1 - DFS 우선 select_walls()에서 백트래킹으로 벽 3개를 빈 공간에 모두 세운다. 그리고 DFS를 이용하여 바이러스를 확산시키키고, 안전지대 개수를 구한다. 바이러스를 확산 시킬 때는lab을 deepcopy하여 복사본에 바이러스를 확산시켜야 한다. 풀이 코드 1 - BFS, itertools 이전 풀이와 달리 itertools의 combinations를 이용하여 벽 위치를 선택하였다. 그리고 벽을 세우고 바이러스를 확산시킬 때 BFS 탐색을 이용하였다. 또한 lab을 deepcopy할 때, deepcopy() 메서드를 사용하지 않고 아래 방법을 사용했다.
[Python] 백준 7569 - 토마토 문제 풀이
Overview BOJ 7569번 토마토 Python 문제 풀이 분류: Graph Traversal (그래프 탐색), bfs [Python] 백준 7576 - 토마토 문제 풀이 를 응용한 문제 문제 페이지 풀이 코드 [Python] 백준 7576 - 토마토 문제 풀이 와 아이디어는 같다. bfs를 응용한 탐색방법으로 익은 토마토
[Python] 백준 7576 - 토마토 문제 풀이
Overview BOJ 7576번 토마토 Python 문제 풀이 분류: Graph Traversal (그래프 탐색), bfs 문제 페이지 풀이 코드 bfs를 응용한 탐색방법으로 익은 토마토와 덜 익은 토마토를 조사한다. 만약 익은 토마토의 상하좌우 위치에 덜익은 토마토가 있는 경우, deque에 해당 위치와 날짜를 저장한다. 그리고 deque에서 pop 될 때는 해당 토마토는 익은 토마토로 처리하고 이전 내용을 반복한다. 위 bfs 응용 탐색을 상자의 토마토가 모두 익거나 덜익은 토마토 만큼 반복하고, 결과를 출력한다.
[JS 자료구조] 그래프 순회(Graph Traversal) - DFS(깊이우선탐색), BFS(너비우선탐색)
그래프 순회(Graph Traversal) 그래프에서 순회하는 코드를 짤 때, 루트가 있는 트리와는 달리 시작점을 정해줘야 한다. 그래프의 한 노드에서 다른 노드로 갈 때 유일한 하나의 길만이 있다는 보장은 없다. 이미 방문한 노드를 다시 방문해야 할 수도 있다. 그래프 순회 사용 예시 P2P 네트워킹 웹 크롤러 최단 거리 찾기 DFS(깊이우선탐색) Explore as far as possible down one branch before "backtracking” DFS(깊이우선탐색)은 다른 형제를 방문( backtracking)하기 전에 한 브랜치에서 가능한 가장 아래까지 깊이 탐색한다. DFS와 BFS 모두, 매개변수로 시
[백준 7569] 토마토
문제 바로가기 문제 분류 가중치가 없는 그래프에서 다중 시작점에서부터 모든 칸까지의 최단 거리를 구하는 문제 출처 - https://solved.ac/contribute/7569 bfs 알고리즘 - [백준 7576] 토마토와 동일 익은 토마토의 위치를 queue에 삽입 queue의 익은 토마토들을 dfs로 순회하며 주변의 안익은 토마토를 익음 처리하고 queue에 삽입. 순회할 때마다 날짜 변수 date를 갱신한다. date를 반환
[백준 7576] 토마토
문제 바로가기 문제 분류 가중치가 없는 그래프에서 다중 시작점에서부터 모든 칸까지의 최단 거리를 구하는 문제 출처 - https://solved.ac/contribute/7576 bfs 알고리즘 익은 토마토의 위치를 queue에 삽입 queue의 익은 토마토들을 dfs로 순회하며 주변의 안익은 토마토를 익음 처리하고 queue에 삽입. 순회할 때마다 날짜 변수 date를 갱신한다. date를 반환 Time Complexity: $$O(mn)$$ Space Complexity: $$O(mn)$$