예나 지금이나

https://www.acmicpc.net/problem/2178    (1, 1) 지점에서 (N, M)의 위치로 가기 위한 최단거리를 구하는 문제입니다.  출발 지점이 주어졌고, 목표 지점이 주어졌습니다. 그래프 탐색 알고리즘을 적용해 볼 수 있겠습니다. 물론 최단경로를 찾는 문제이기 때문에 다익스트라 알고리즘과 같은 최단경로 알고리즘을 사용해도 되겠습니다.그래프 탐색 알고리즘의 종류에는 BFS와 DFS가 있는데 이 문제는 BFS를 사용해서 풀어야합니다.DFS는 최단거리를 보장해주지 못하기 때문입니다. 그에 비해 BFS는 시작지점과 도착지점의 최단거리를 보장합니다. from collections import deque# 상하좌우 방향dx = [0, 0, -1, 1]dy = [1, -1, 0, 0]def..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일www.acmicpc.net       풀이 과정 그래프 이론을 배운 상태이며, 이 문제를 그래프 탐색으로 풀어야겠다고 생각이 들었으면 구현 자체는 크게 어려운 문제는 아니라고 생각합니다. 그래프 탐색 알고리즘을 사용할 때 DFS를 쓸 것인지, BFS를 쓸 것인지만 결정하면 됩니다. 하지만 이 문제에서 DFS는 적합하지 않습니다. 저희는 노드를 탐색하는 것이 목표가 아니라, 시작 지점에서 도착 지점까지..

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 알고리즘을 알아야합니다.DFS란 그래프의 깊이 우선 탐색 알고리즘이고, BFS란 그래프의 너비 우선 탐색 알고리즘을 의미합니다. DFS(깊이 우선 탐색)은 루트 노드에서부터 탐색을 시작해서 하나의 분기가 끝날때까지 타고 내려가서 탐색을 수행한 다음, 탐색이 끝나면 다음 분기로 넘어가서 탐색을 ..