Approach 맨 처음 접근은 모든 벽에 대해서 BFS나 DFS를 수행하는 것이였다. 일종의 브루트포스적인 접근이였는데, 이 경우 시간초과가 발생하게 된다. 조금 더 단순하게 접근하면, 해당 벽을 기준으로 상하좌우의 component를 연결하는 느낌으로 이해해주면 된다. 이를 위해서는 각 위치에서 어떠한 component에 속하는지를 알아야하고, 각 component 별로 속한 개수를 따로 저장해두면 된다. 발상은 https://viyoung.tistory.com/327의 2번째 접근 방법을 풀어봤던 경험을 바탕으로 쉽게 할 수 있었다. 일종의 visited 배열을 component에 대응시키는 배열로 사용한 것이다. [백준 10265번] [DFS / SCC] MT Approach 위 문제에서 나타나게..

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(..

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..

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..

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..

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를 처리하지 않고 이동할 공간이 영역 내부이고 불에 해당하지 않으면 이동해주면 된다. 왜..

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..

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..