너비 우선 탐색

문제 풀이 그래프 탐색, 누적합 문제이다. 횡단보도의 칸 중에서 물이 빠질 칸을 BFS로 탐색한다. BFS의 시작은 하수구 칸에서 시작한다. 현재 탐색 중인 칸의 상하좌우 칸 중에서, 현재 칸의 높이 이상인 칸은 물이 빠진다. 신발을 딛을 수 있는 방법의 수는 2차원 배열의 누적합으로 구한다. 위의 그림에서 초록색 영역의 합을 구해보자. 파란색 영역을 모두 한번씩 더한다면 빨간색 영역은 두 번 더해진다. 그러므로, 파란색 영역을 한번 더하고, 빨간색 영역을 한번 빼면 초록색 영역의 합을 구할 수 있다. for (int i = 1; i N >> M; cin >> h >> w; for (int i = 1; i road[i][j]; } } memset(water, true, sizeof(water)); int..

문제 풀이 구현, 시뮬레이션 문제이다. 원판을 2차원 배열로 생각하고 처리한다. 원판을 회전시킬 때, 끝과 처음이 연결되어 있는걸 주의해야 한다. 원판과 인접한 수를 탐색할 때, BFS로 인접한 수가 현재 수와 같은 원판의 위치를 탐색한다. 탐색의 결과로 수를 지울지, 평균을 구할지를 결정한다. 코드 #include #include #include #include using namespace std; typedef struct { int x; int y; }type; queue bfs; int circles[51][51]; bool visited[51][51]; int move_x[4] = { 0, 0, 1, -1 }; int move_y[4] = { 1, -1, 0, 0 }; int main() { i..

문제 풀이 구현, 시뮬레이션, 너비 우선 탐색, 그래프 탐색 문제이다. 터질 뿌요들을 탐색할 때, BFS를 이용한다. 상하좌우로 같은 색상의 뿌요들을 탐색했을 때, BFS 탐색의 횟수가 4이상이라면 터질 뿌요들이다. 이 것을 queue explode의 형태로 저장한다. explode 큐를 꺼내면서 뿌요를 터트린다. 터진 뿌요에 해당하는 필드는 '.'으로 값이 변한다. 밑에 빈 공간이 있는 뿌요들은 아래로 떨어져야 한다. 아랫줄부터 검사하면서 현재 검사하는 타일의 값이 '.'일 경우, 해당 타일 바로 위에 있는 뿌요 타일과 값을 바꾼다. 다시 explode 큐를 채우기 위해 BFS로 터질 뿌요들을 탐색하고, explode가 모두 비워질 때까지 반복한다. 코드 #include #include #include..

문제 풀이 종이의 가장자리는 모두 비어있으므로 (0, 0)에서부터 BFS를 시작하여 외부 공기를 모두 방문한다. 방문과 동시에 해당 공기의 상하좌우로 치즈가 있는지 검사하여 치즈마다 공기와 접촉한 횟수를 구한다. 각 치즈를 검사하여 공기와 2번 이상 접촉했다면 해당 치즈를 삭제하고 다시 BFS를 실시한다. 모든 치즈가 녹았다면 BFS를 중지한다. 코드 #include #include #include using namespace std; typedef struct { int x; int y; }type; queue q; int ground[101][101]; int visited[101][101]; int cheese_ground[101][101]; int move_x[4] = { 0, 0, 1, -1 }..

문제 풀이 BFS를 이용하여 해결한다. 이전에 이동했던 위치인 visited를 큐에 넣을 때 true로 세팅하지 않고 꺼낼 때, 세팅하여 중복된 경로도 추가될 수 있도록 한다. 이동할 수 있는 방법 별로 큐에 넣는다. 코드 #include #include #include #include using namespace std; typedef struct { int X; int dist; }type; queue q; bool visited[100002]; map answer_map; int main() { int N, K; int answer = INT_MAX; cin >> N >> K; q.push({ N, 0 }); visited[N] = true; while (!q.empty()) { type curre..

문제 풀이 DP와 그래프 탐색으로 풀 수 있다. 코드 그래프 탐색 #include #include #define VER 0 #define HOR 1 #define DIA 2 using namespace std; typedef struct { int x; int y; int dir; }type; // 파이프의 방향에 따른 이동 위치 vector move_x = { {0, -1, 1}, {-1, 1, 1}, {0, 1, 1} }; vector move_y = { {1, -1, 1}, {-1, 0, 1}, {1, 0, 1} }; // 파이프의 방향과 이동 위치에 따른 검사 위치 int check_x[3] = { 1, 1, 0 }; int check_y[3] = { 0 ,1, 1 }; //vector check..