BFS(너비 우선 탐색) 정의 너비 우선 탐색(Breadth-first search, BFS)은 그래프 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 자료구조 큐를 이용하여 구현. 그림에서 보면 회색은 현재 큐에 들어가있는 정점이고 검은색은 방문완료한 정점이다. 알고리즘 (2차원 배열기준) 1. 큐를 이용하여 시작점을 먼저 push . 2. 큐가 비워 질때까지 반복 3. 시작점을 중심으로 상,하,좌,우 중 탐색가능한지점을 큐에 넣어주고 탐색이 끝 날때 까지반복. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..

문제 링크 : https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때 www.acmicpc.net 문제 설명 1. 각 마을에는 한명의 학생이살고 각 마을마다 파티가 열린다. 2. 각 마을로 이동하는 단방향 그래프가 주어짐 3..

문제 링크 : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) www.acmicpc.net 문제 설명 1. 방향 성이 없는(양방향) 그래프가 주어지고 시작점 부터 끝점 까지의 최단거리를 출력. 2. 단, 주어지는 2개의 정점을 방문하여..

문제 링크 : https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 www.acmicpc.net 문제설명 1. 방향그래프와 시작 점이 주어지고 , 시작점에서 모든정점까지의 최단 거리를 출력. 2. 만약 이동 할 수 없다면..

문제링크 : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 문제 설명 1. 배열의 크기 N,M이주어짐 2. 현재 위치 (1,1) 에서 (N,M)까지 가는데 0은 그냥 이동 할 수있고 1은 벽이 세워져 있는곳이다. 3. 목적지 까지 도달하기 위해서는 최소 몇개의 벽을 부셔야 할까 ? 알고리즘 1. 먼저 입력이 띄어서 입력 받지 않기 때문에 scnaf("%1d",&map[i]..

문제링크 : https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입 www.acmicpc.net 문제설명 1. NxN 행렬의 크기 N이주어지고 각 행렬에 정수가 채워진다. 2. (1,1)에서 (N,N)..