BFS

문제 : https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 어떤 문제인가? 이 문제는 기존의 2차원에서 움직이던 그래프 탐색이 아니라 3차원으로 이동해야 한다. 시작 좌표 S부터 움직여가며 도착 좌표 E까지 이동하는 게 걸리는 시간을 출력하면 된다. 접근 방법 int dx[6] = {1, -1, 0, 0, 0, 0}; int dy[6] = {0, 0, 1, -1, 0, 0}; int dz[6] = {0, 0, 0, 0, 1, -1}; 위의 배열들은 x..

문제 : https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 어떤 문제인가? 아주 간단한 문제이다. 기존의 상, 하, 좌, 우로 그래프를 탐색하던 방법에서 나이트의 이동 방식처럼만 움직이며 탐색하면 되는 문제이다. 나이트의 시작 위치와 도착 위치가 주어졌을 때 도착하는 최소 횟수를 출력하면 된다. 접근 방법 int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[8] = {1, -1, 2, -2, 2, -2, 1, -..

문제 : https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 어떤 문제인가? 존재하는 정점들 중 한 정점에서 다른 모든 정점으로 가는 거리들을 모두 더한 값을 케빈 베이컨 수라고 한다. 이때, 케빈 베이컨수가 가장 작은 정점의 번호를 출력하면 된다. 접근 방법 먼저 정점 간의 거리를 측정해야 하기 때문에 bfs를 사용하기로 했다. vector graph[5001]; bool visited[101]; ..

문제 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 어떤 문제인가? 입력된 그래프를 탐색해나가며 모든 토마토가 익는데 걸리는 최소 날짜를 출력하는 문제이다. 접근 방법 int tomato[1001][1001]; bool visited[1001][1001]; int n, m; 토마토 상자의 값을 저장할 이차원 배열과 방문 여부를 저장할 이차원 배열, n과 m을 선언해준다. queue q; 탐색에 필요한 큐를 선언해준다. 이때..

문제 : https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 어떤 문제인가? 각 위치의 높이가 존재한다. 따라서, 0부터 최대 높이까지 모든 경우를 살펴봐야 한다. 잠기는 높이마다 생기는 연결 요소들의 개수가 바뀌게 된다. 이때, 어떤 높이에서 생기는 연결 요소의 최대 개수를 출력하면 된다. int map[101][101]; bool visited[101][101]; int n; 위치들의 높이를 저장할 이차원 배열과 방문 여부를 저장할 이차원 배열, n을..

문제 : 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 어떤 문제인가? 그래프를 입력받고 연결 요소의 개수를 출력하면 된다. 이 문제를 풀기위해선 먼저 연결 요소가 무엇인지 알아야 한다. 간단하게 말하면 나누어진 각각의 그래프들을 연결 요소라고 한다. 문제의 첫 번째 예시대로 입력을 받으면 1-2-5, 3-4-6이 연결된 두 개의 연결 요소가 존재하는 것이다. 접근 방법 한 정점을..

문제 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 어떤 문제인가? n*m 크기의 공간에서 0과 1로 미로를 만든다. 1은 지나갈 수 있고 0은 지나갈 수 없는 곳이다. 이때 왼쪽 위부터 출발해 오른쪽 아래까지 갈 수 있는 최소 거리를 구하면 된다. 접근 방법 이동의 가중치가 없는 그래프에서 최단 경로를 구하는 것이기 때문에 bfs를 통해 접근하였다. int miro[101][101]; bool visited[101][101]; 먼저 미로를 저장할 이차원 배열과 방문처리..

문제 : 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를 통해 그래프를 탐색하는 순서를 출력하면 되는 간단한 문제이다. 접근 방법 bool visited[1001]; vectorgraph[10001]; 먼저 그래프를 저장할 벡터와 정점의 방문 여부를 저장할 배열이 필요하다. int n,m,v; cin >> n >> m >> v; 문제에서 주어진 변수들을 ..

문제 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 어떠한 그래프에 대한 깊이 우선 탐색과 너비 우선 탐색 결과를 각각 출력하면 되는 문제이다. 주의해야 할 점은 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문한다는 것이다. 따라서 그래프를 sort함수를 통해 오름차순으로 정렬해줘야 한다. 입력받은 v부터 dfs를 실행한 결과를 출력하고 그래프를 다시 초기 상태로 돌려놔 bfs..