문제 링크: https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net BFS BFS로 dx, dy 방향으로 최단거리를 구하는 문제에서 dz 방향이 추가된 문제입니다. 3차원 배열 입력과, dz방향 추가만 고려하면 구현하는 건 2차원과 동일합니다. int dx[6] = { 0,0, 1, -1, 0, 0 }; //동 서 남 북 상 하 int dy[6] = { 1,-1, 0, 0, 0 , 0 }; int dz[6] = { 0, 0, 0, 0 , 1, -1 }; 1..

문제 링크: https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 기본적인 그래프 BFS를 구현하면 되는 문제입니다 다음 정점의 위치는 다음과 같습니다. 위층: cur + U 아래층: cur - D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include #include..

문제 링크:https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net BFS 섬의 육지에서 시작해서 BFS로 다른 섬의 육지에 최초로 만나는 지점이 다리를 놓을 수 있는 방법 중에 하나입니다. 그래서 문제를 해결하기 위해서 1. bfs로 섬을 구분한다. 10 1 1 1 0 0 0 0 2 2 2 1 1 1 1 0 0 0 0 2 2 1 0 1 1 0 0 0 0 2 2 0 0 1 1 1 0 0 0 0 2 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 ..

문제 링크: https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net BFS 이 문제는 4179번 문제에서 테스트 케이스가 추가된 문제입니다. 각 테스트 케이스마다 배열을 초기화하는 작업만 추가하면 됩니다. https://seokjin2.tistory.com/67 [백준 4179번] 불! 문제 링크:https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, ..

문제 링크:https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net BFS 기본적인 BFS 최단거리 문제랑 똑같은데 방향만 8방향으로 설정해주면 됩니다. int dx[8] = {-2, -1, 1, 2, -2, -1, 1, 2}; int dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32..

문제 링크:https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 정상인에 대해서 BFS를 돌리고, 적록색약에 대해서 BFS를 돌리면 되는데 적록색약은 빨간색과 초록색을 같은 색으로 보니깐 board[i][j]의 값이 R이면 G로 바꿔준 뒤 BFS를 돌리면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37..

문제 링크:https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net BFS 알고리즘 이문제는 여러 개의 시작점을 갖는 불에 대해서 BFS를 먼저 돌려서 불의 도착 시간을 구한 뒤에, BFS를 사용해서 각 위치에 대해서 지훈이가 불 보다 먼저 갈 수 있으면 그 위치에 지훈이의 도착 시간을 갱신하면 됩니다. 여러 개의 시작점을 갖는 불을 동시에 BFS로 출발시키는 방법은 처음 시작점을 모두 큐에 넣고 기본적인 BFS을 진행하면 됩니다. 지훈이..

문제 링크:https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS 이문제는 기본적인 bfs를 사용해서 최단거리를 구하면 됩니다. 그런데 익은 토마토가 여러 개이면 모든 익은 토마토에 대해서 동시에 출발을 해야 됩니다. 시작점을 여러개 두고 bfs를 동시에 진행하는 방법은 시작점을 모두 queue에 넣고 시작하면 됩니다. (그러면 번갈아가면서 push, pop을 하기 때문에 동시에 출발시킨 효과) 1 2 3 4 5 6 7 8 9 ..