https://www.acmicpc.net/problem/2206 (1,1)에서 (n,m)까지의 최소 경로를 구하는 문제다. 조건: 길은 0, 벽은 1로 표현되어 있으며 벽은 최대 1회까지 부술 수 있다.평범하게 BFS로 구현하되 벽을 부순적이 있는지 확인할 수 있어야한다. 예전에 https://www.acmicpc.net/problem/31404에서 특정위치에 반복해서 들어가는 것 뿐만 아니라 들어오는 방향까지 고려해서 3차원 배열을 이용하여 문제를 해결했었다. 똑같은 문제라고 생각했고 visited배열을 visited[x][y][cnt]로 설정하여 cnt에 벽을 부쉈는지 확인하는 배열을 추가했다. 배열이 3차원이 된 것만 빼면 나머지는 well-known한 BFS탐색이다.#include #includ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 백준 2178번과 거의 똑같은 문제라고 할 수 있다. 2178번에서 미로를 탐색할때 몇번만에 갈 수 있는지 깊이 지도를 그려서 문제를 해결했었다. 이번 문제도 마찬가지로 어차피 하루당 한 칸씩 토마토가 익으므로 깊이지도를 그리면된다. 미로 문제와 다른점은 미로는 BFS의 출발점이 하나였지만, 토마토는 시작할 때 부터 여러개가 익어 있을 수 있기 때문에 queue에 익은 토마토를 모..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제를 보자마자 BFS써야겠다라는 생각뿐. 단순하게 농장을 2차원 배열로 받아서 배추가 있는 부분만 1로 표시한다. 농장 전체를 훑으면서 배추가 있고 아직 탐색을 안한 부분이면 BFS를 돌리면 된다. BFS가 끝나면 그 부분에 배추흰지렁이가 필요하므로 count += 1을 해주면 된다. 그렇게 농장 전체를 훑으면 인접한 부분당 배추흰지렁이가 있는 것으로 탐색되므로 농장을 탐색하면서 BFS를 한 횟수가 결국 배..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 특정 위치까지 몇칸을 가야하는지 구하는 문제로 BFS를 사용하여 해결하였다. 탐색을 하면서 갈래길을 탐색해야하므로 상/하/좌/우를 검사하기 위한 좌표 리스트를 Cross_x, Cross_y로 만들었다. 그리고 BFS를 작성하고 나니 어떻게 특정 위치까지의 거리를 계산할까 하다가 BFS로 탐색한 깊이 지도를 하나 만들었다. 이 지도는 처음 시작부분부터 최소 몇번을 가야지 도달할 수 있는지 저장해놓는 지도로 BFS를 하면서 저장한다..