문제 링크: https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭..

문제 링크: 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을 진행하면 됩니다. 지훈이..