BFS

백준 16928번 www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제 : 뱀과 사다리 게임을 즐겨하는 큐브 러버는 어느 날 궁금한 점이 생겼다. 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까? 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10 × 10이고, 총 100개의 칸으로 나누어져 있는 보..

그래프의 탐색 대표적인 그래프 탐색인 DFS, BFS에 대해서 알아보자. 그래프 탐색의 목적은 임의의 정점에서 시작해서 연결되어있는 모든 정점들을 한 번씩 방문하는 것이다.! 1. DFS (Depth First Search) : 깊이 우선 탐색 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 갈 수 없으면 이전 정점으로 돌아가서 모든 정점을 방문한다. (재귀를 사용할 수도 있다!) 이 그래프에 dfs를 사용해보자. 1에서 시작하고 어떤 정점을 방문하면 스택에 넣고 check[i] 에 1을 표시하자. 현재 정점 : 1 순서 : 1 스택 : 1 i 1 2 3 4 5 6 check[i] 1 0 0 0 0 0 1 다음에 갈 수 있는건 2, 5 둘 중에 하나로 가면 된다. 2로 가보자 현재 정점 : 2 순서 ..