문제: www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제풀이 같은 이름의 7576번 토마토 문제와 다른 점은 토마토가 3차원으로 주어진다는 것이다. 3차원 배열에 대하여 BFS를 진행하여 최단거리를 구하면 된다. 이때 토마토(1)가 주어진 곳의 좌표는 토마토가 익을 수 있는 시작점이므로 큐에 push 해준다. 코드 #include #include #include using namespace std; int dz[6] = {-1,1,..

문제: www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제풀이 흰 배추 지렁이는 인접한 배추로 이동할 수 있으므로 서로 인접한 배추가 몇 군데 있는지를 알아내는 문제였다. BFS를 이용하여 방문하지 않은 배추를 찾을 때마다 카운트를 증가시켜 서로 인접한 배추가 몇 군데 있는지를 알아냈다. 코드 #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int board[50..

문제: www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 문제풀이 BFS를 이용한 최단거리 문제 거리 배열을 2개를 선언하고 배열 1은 불의 BFS 순서를 저장하고 배열 2는 지훈이의 BFS 순서를 저장하였다. 배열 2의 BFS 순서를 저장할 때 저장하기 전 배열 1의 값과 비교하여 배열 1의 값이 배열 2의 값보다 작거나 같으면 불이 붙어있거나 지훈이와 불이 동시에 도착할 수 있는 즉, 갈 수 없는 좌표이므로 continue 해준다. 코드 #i..

문제: www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제풀이 일차원 선 위에서 BFS를 이용하여 최단거리를 구하였다. 이때 수빈이와 동생의 위치는 0부터 100, 000까지이지만 수빈이는 현재 거리의 2배를 순간 이동할 수 있기 때문에 거리 배열을 100,000의 두배인 200,001로 선언하였다. 코드 #include #include using namespace std; int dist[200001]; int main(){ i..

문제: www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제풀이 BFS를 이용해 최단거리를 구하는 문제이다. 이 문제는 시작점(익은 토마토)이 여러 곳이므로 시작점을 모두 큐에 넣어준다. 코드 #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int board[1000][1000]; int dist[1000][1000]; int main(..

문제: www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제풀이 BFS를 이용해 (1, 1) 부터 (N, M) 까지의 최단거리를 구하는 문제이다. 미로가 공백없이 한 행씩 입력되므로 맵을 문자열로 선언했다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin>>N>>M; string board[100]; //한 행씩 입력되므로 문자열로 선..