Algorithm/Graph

문제https://www.acmicpc.net/problem/12851 문제 분석해당 문제는 BFS 유형이다.  왜 BFS인가?처음에는 DP라고 생각을 했다. 이상하게 유독 BFS문제를 보면 DP라고 생각할 때가 종종 있는 것 같다... 하지만 이 문제가 BFS유형임에 확실한 것은 (물론 DP로도 풀려고하면 풀 수도 있겠지만) "가장 빠른 시간" 과 "가장 빠른 시간으로 찾는 방법" 이라는 키워드가 있기 때문이다. 가장 빠른 방법 중에서도 특히나 가중치가 없는 그래프의 경우에는 BFS임이 자명하다. 만약 가중치가 있을 경우에는 다익스트라 알고리즘을 사용해야한다. 특히나 트리일 경우에는, BFS는 반드시 "최단경로"를 거칠 수 밖에 없다. 왜냐하면, 해당 노드 간의 경로가 단방향, 또한 하나만 존재하기 때..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 다음 문제는 dfs와 bfs의 가장 기초적인 문제다. 문제 풀이법은 딱히 중요한건 아닌 것 같고, 이 문제를 사실 9개월 전에 한번 풀었다가 감이 죽은 지금 다시 한번 풀었는데 메모리랑 실행시간이 너무 크게 비교가 돼서...(물론 9개월 전 코드가 더 아름다웠다.) 마음이 아파서 왜 그런지 비교해보도록 하겠다. 9개월 전 똑똑했던 나의 코드 #include #..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이과정 ①문제 바라보기 간단한 graph이론 문제다. DFS문제고, 이해를 위해서 문제에서 제시한 예제 2개를 간선과 노드로 표현해봤다. 위의 그림을 보면 1,2,5가 연결되어있고 3,4,6이 연결되어있음을 확일할 수 있다. 따라서 출력값이 2가 되는 것이며, 두번째 그림을 보면 1~6이 모두 어떻게든 연결되어있기에 출력값이 1이 됨..

미로 찾기 문항은 BFS를 이용했을 때 매우 효과적으로 해결할 수 있다. Why? : BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다. 그러므로 (1,1)지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다. 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다. from collections import deque # N, M을 공백으로 구분하여 입력받기 n, m = map(int,input().split()) # 2차원 리스트의 맵 정보 입력받기 graph = [] for i in range(n): graph.append(list(map(int,input()))) # 이동할 네 방향 정의(상,하,좌,우) dx = [-..

DFS/BFS 는 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘이다. 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다. 자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. 그중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다. 삽입(Push): 데이터를 삽입한다. 삭제(Pop): 데이터를 삭제한다. 스택 (~=박스 쌓기) 스택은 선입후출(First In Last Out)구조 또는 후입선출(Last In ..