[알고리즘] 그래프 탐색 기법을 코드로 이해하기
1. 그래프 그래프는 광범위한 분야에서 활용되고 있는 자료구조이다. 그러다보니 코딩테스트 문제 출제 1순위이다. 그래프는 정점과 간선의 집합으로 하나의 간선은 두 개의 정점을 연결한다. 그래프는 G=(V, E)로 표현하는데 간선에 방향이 있는 그래프를 방향그래프, 간선에 방향이 없는 그래프를 무방향그래프라고 한다. V = 정점의 집합, E = 간선의 집합 2. 그래프 탐색 그래프에서는 너비우선탐색(BFS)과 깊이우선탐색(DFS) 방식으로 모든 정점을 방문할 수 있다. 2.0 그래프 코드 G = { 1: set([3, 5]) 2: set([3, 4, 6]), 3: set([1, 2, 6]), 4: set([2]), 5: set([1]), 6: set([2, 3]) } 2.1 BFS BFS는 큐를 사용해 임..
[Python] 백준 12851번 문제, 숨바꼭질 2
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 수빈이가 동생과 숨바꼭질 하고 있는데 수빈이가 동생을 찾는 가장 빠른 시간이 몇 초 후이며, 가장 빠른 시간으로 찾는 방법이 몇 가지인지 구하는 문제이다. 수빈이가 X(0 ≤ X ≤ 100,000)에 있다고 가정 했을 때, 1초에 { X-1, X+1, 2X }으로 이동할 수 있다. 이렇게 몇 초후에 동생이 있는 K(0 ≤ K ≤ 100,000)에 도달하는지 구..
