bfs
-
Approach https://viyoung.tistory.com/334 [백준 2206번] [BFS] 벽 부수고 이동하기 Approach 표면적으로 보면 BFS 대표 유형과 유사해보인다. 다만, 일반적인 문제와 달리 1칸 벽을 뚫을 수 있다는 측면을 추가적으로 고려해야한다는 점에서 어렵다고 할 수 있다. 잘 생각해보면, 무 viyoung.tistory.com 위 문제와 거의 동일하다. 다만, 부술 수 있는 벽의 개수가 k개이므로 visited배열의 마지막 차원의 공간을 k + 1개만큼 할당해주면 된다. 추가적으로 방문여부 체크를 할 때는 반드시 queue에 push할 pos를 기준으로 체크해주어야 한다. Code #include #define fastio ios_base::sync_with_stdio(..
[백준 14442번] [BFS] 벽 부수고 이동하기 2Approach https://viyoung.tistory.com/334 [백준 2206번] [BFS] 벽 부수고 이동하기 Approach 표면적으로 보면 BFS 대표 유형과 유사해보인다. 다만, 일반적인 문제와 달리 1칸 벽을 뚫을 수 있다는 측면을 추가적으로 고려해야한다는 점에서 어렵다고 할 수 있다. 잘 생각해보면, 무 viyoung.tistory.com 위 문제와 거의 동일하다. 다만, 부술 수 있는 벽의 개수가 k개이므로 visited배열의 마지막 차원의 공간을 k + 1개만큼 할당해주면 된다. 추가적으로 방문여부 체크를 할 때는 반드시 queue에 push할 pos를 기준으로 체크해주어야 한다. Code #include #define fastio ios_base::sync_with_stdio(..
2021.12.14 -
Approach 표면적으로 보면 BFS 대표 유형과 유사해보인다. 다만, 일반적인 문제와 달리 1칸 벽을 뚫을 수 있다는 측면을 추가적으로 고려해야한다는 점에서 어렵다고 할 수 있다. 잘 생각해보면, 무시했는지 여부도 그래프 탐색 과정에서 고려해주면 된다. 일종의 dp에서 고려해야할 정보가 1개 늘으면 차원을 한 개 늘려잡는 것처럼, visited 배열의 차원을 1개 늘려주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; class point{ public: int z, x, y; point(){}; point(int a, in..
[백준 2206번] [BFS] 벽 부수고 이동하기Approach 표면적으로 보면 BFS 대표 유형과 유사해보인다. 다만, 일반적인 문제와 달리 1칸 벽을 뚫을 수 있다는 측면을 추가적으로 고려해야한다는 점에서 어렵다고 할 수 있다. 잘 생각해보면, 무시했는지 여부도 그래프 탐색 과정에서 고려해주면 된다. 일종의 dp에서 고려해야할 정보가 1개 늘으면 차원을 한 개 늘려잡는 것처럼, visited 배열의 차원을 1개 늘려주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; class point{ public: int z, x, y; point(){}; point(int a, in..
2021.12.14 -
Approach https://viyoung.tistory.com/331 위 문제와 접근방법이 기본적으로 동일하다. BFS 2개를 통해 해결해주면 된다. [백준 5427번] [BFS] 불 Approach BFS를 2개 돌리면 된다. 시간 단위로 불과 상근이 모두 1칸씩 이동할 수 있으므로 상근이를 먼저 이동시키고 불을 이동시켜서 결과적으로 상근이가 경계선 밖을 넘는지 여부만 체크해주면 viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move..
[백준 3055번] [BFS] 탈출Approach https://viyoung.tistory.com/331 위 문제와 접근방법이 기본적으로 동일하다. BFS 2개를 통해 해결해주면 된다. [백준 5427번] [BFS] 불 Approach BFS를 2개 돌리면 된다. 시간 단위로 불과 상근이 모두 1칸씩 이동할 수 있으므로 상근이를 먼저 이동시키고 불을 이동시켜서 결과적으로 상근이가 경계선 밖을 넘는지 여부만 체크해주면 viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move..
2021.12.14 -
Approach https://viyoung.tistory.com/331와 동일하다. [백준 5427번] [BFS] 불 Approach BFS를 2개 돌리면 된다. 시간 단위로 불과 상근이 모두 1칸씩 이동할 수 있으므로 상근이를 먼저 이동시키고 불을 이동시켜서 결과적으로 상근이가 경계선 밖을 넘는지 여부만 체크해주면 viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; int r[1000][100..
[백준 4179번] [BFS] 불!Approach https://viyoung.tistory.com/331와 동일하다. [백준 5427번] [BFS] 불 Approach BFS를 2개 돌리면 된다. 시간 단위로 불과 상근이 모두 1칸씩 이동할 수 있으므로 상근이를 먼저 이동시키고 불을 이동시켜서 결과적으로 상근이가 경계선 밖을 넘는지 여부만 체크해주면 viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; int r[1000][100..
2021.12.14 -
Approach BFS를 2개 돌리면 된다. 시간 단위로 불과 상근이 모두 1칸씩 이동할 수 있으므로 상근이를 먼저 이동시키고 불을 이동시켜서 결과적으로 상근이가 경계선 밖을 넘는지 여부만 체크해주면 된다. 이미지로 가시화한 결과는 다음과 같다. https://m.blog.naver.com/kks227/220785747864 너비 우선 탐색(Breadth-First Search) (수정 2018-11-22) 자, 이제 빨리 DFS의 반대 개념인 BFS에 대해 배워보죠. BFS는 너비 우선 탐색(breadth-first sea... blog.naver.com 다만, 불의 경우에는 굳이 불인 경우에 대해서는 visited를 처리하지 않고 이동할 공간이 영역 내부이고 불에 해당하지 않으면 이동해주면 된다. 왜..
[백준 5427번] [BFS] 불Approach BFS를 2개 돌리면 된다. 시간 단위로 불과 상근이 모두 1칸씩 이동할 수 있으므로 상근이를 먼저 이동시키고 불을 이동시켜서 결과적으로 상근이가 경계선 밖을 넘는지 여부만 체크해주면 된다. 이미지로 가시화한 결과는 다음과 같다. https://m.blog.naver.com/kks227/220785747864 너비 우선 탐색(Breadth-First Search) (수정 2018-11-22) 자, 이제 빨리 DFS의 반대 개념인 BFS에 대해 배워보죠. BFS는 너비 우선 탐색(breadth-first sea... blog.naver.com 다만, 불의 경우에는 굳이 불인 경우에 대해서는 visited를 처리하지 않고 이동할 공간이 영역 내부이고 불에 해당하지 않으면 이동해주면 된다. 왜..
2021.12.14 -
Approach https://viyoung.tistory.com/328와 완전히 동일~ [백준 7562번] [BFS] 나이트의 이동 Approach 2178번과 다를바가 없음. 다만, 이동하는 양상이 총 8개인점만 다르다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii;.. viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; class point { public: in..
[백준 7569번] [BFS] 토마토Approach https://viyoung.tistory.com/328와 완전히 동일~ [백준 7562번] [BFS] 나이트의 이동 Approach 2178번과 다를바가 없음. 다만, 이동하는 양상이 총 8개인점만 다르다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii;.. viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; class point { public: in..
2021.12.13 -
Approach https://viyoung.tistory.com/326 이 문제를 3차원으로 확장한 것과 크게 다르지 않다. [백준 2178번] [BFS] 미로 탐색 Approach DFS가 아니라 BFS로 해야한다. DFS로 하게 되면 모든 가능한 케이스를 모두 조사해보아야 하는데, 그 경우는 $4^{NM}$이므로 시간초과가 난다. 추가적으로 큐에 여러번 들어갈 수 있는 가능성 viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; class point{ public: int z; int x; int y; point(){} point(i..
[백준 6593번] [BFS] 상범 빌딩Approach https://viyoung.tistory.com/326 이 문제를 3차원으로 확장한 것과 크게 다르지 않다. [백준 2178번] [BFS] 미로 탐색 Approach DFS가 아니라 BFS로 해야한다. DFS로 하게 되면 모든 가능한 케이스를 모두 조사해보아야 하는데, 그 경우는 $4^{NM}$이므로 시간초과가 난다. 추가적으로 큐에 여러번 들어갈 수 있는 가능성 viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; class point{ public: int z; int x; int y; point(){} point(i..
2021.12.13 -
Approach 2178번과 다를바가 없음. 다만, 이동하는 양상이 총 8개인점만 다르다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int r[300][300]; bool visited[300][300]; int move_x[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int move_y[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; int main(void){ fastio; int t; cin >> t; while(t--){ memset(r, 0, sizeof(r)); memset(visited..
[백준 7562번] [BFS] 나이트의 이동Approach 2178번과 다를바가 없음. 다만, 이동하는 양상이 총 8개인점만 다르다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int r[300][300]; bool visited[300][300]; int move_x[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int move_y[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; int main(void){ fastio; int t; cin >> t; while(t--){ memset(r, 0, sizeof(r)); memset(visited..
2021.12.13