BOJ/BFS
[C++] BOJ 7576 / BFS 응용(시작점이 여러 개)
문제 분석 BFS 기초 문제를 풀다보면 만나는 문제이다. 문제의 조건에 토마토의 개수가 1개로 고정된다는 말이 없으므로, 토마토의 개수가 여러 개 일 수 있으며, 이말은 즉 BFS를 돌릴 때의 시작점이 여러개라는 뜻이다. 해결 방법 시작점이 여러 개인 BFS의 경우, 모든 시작점을 큐에 넣고 BFS를 돌면 자연스럽게 거리가 구해진다. 코드 #include #include #include using namespace std; #define X first #define Y second int board[1001][1001]; bool vis[1001][1001]; int dx[4] = {1,0,-1,0}; int dy[4] = {0,-1,0,1}; int main() { ios::sync_with_stdio..
BFS 기본 틀
BFS는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. BFS에 대해서는 자료구조와 알고리즘 시간에 배웠으므로, 개념에 대한 자세한 정리는 따로 하지 않겠다. BFS를 구현하는 기본 틀은 아래와 같다. 반복 숙달을 통하여 자기것으로 만드는 것이 좋다. #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int board[502][502] bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장 int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미 int main(void){ queue q; vis[0][0] = 1; //..