Approach 문제 설명이 난해해서 꽤 많이 틀렸다.. 일단, 연산을 k번 했을 때의 상황을 묻는 것이므로 BFS문제임을 쉽게 직감할 수 있다. 기본적으로 다음 문제 컨셉과 비슷하기 때문이다. https://viyoung.tistory.com/338 [백준 9019번] [BFS] DSLR Approach 최소한의 명령어를 찾는 것이므로 BFS를 활용하면 된다는 것을 쉽게 파악할 수 있다. https://viyoung.tistory.com/337 이 문제와 접근방법이 매우 유사하다. [백준 16397번] [BFS] 탈출 Approach 잘 생.. viyoung.tistory.com 이 문제가 좀 어려운 이유는 정확히 K번 움직였을 때 나올 수 있는 수들 중 최댓값을 구해야한다는 지점이다. 왜냐하면 단순히..

Approach 최소 이동 횟수를 물어보는 지점에서 BFS 문제를 추측할 수 있다. 이 경우에는 이동하는 기준이 3 x 3 상태이다. 따라서 해당 3 x 3 배열을 일종의 정점처럼 취급하여 BFS를 돌리면 된다. (0의 위치를 기준으로 탐색을 해도 된다는 생각이 들 수 있으나, 0의 위치가 같아도 행렬이 달라질 수 있기 때문에 이 방법으로는 이 문제를 풀 수 없다.) 다만, 배열을 직접적으로 넣으면 메모리 초과에 걸리므로 string 자료형을 활용하여서 메모리를 상당히 줄였다. BFS에 들어가는 정보가 좌표가 아니라 배열이라는 점이 매우 독특했던 문제이다. (참고 : https://blog.naver.com/kks227/220785747864) 너비 우선 탐색(Breadth-First Search) (수..

Approach 최소한의 명령어를 찾는 것이므로 BFS를 활용하면 된다는 것을 쉽게 파악할 수 있다. https://viyoung.tistory.com/337 이 문제와 접근방법이 매우 유사하다. [백준 16397번] [BFS] 탈출 Approach 잘 생각해보면 최대 T번 누를 수 있다는 명제를 T번 이동할 수 있다로 바꾸고, 버튼 A와 B를 누르고 나오는 숫자를 기준으로 생각해보면 비둘기집의 원리에 따라서 총 99999가지 경우의 수 viyoung.tistory.com 기본적으로 숫자를 기준으로 방문배열을 체크해야한다는 점에서 완전히 동일하다. 다른 지점은, 명령어를 기억해야한다는 점인데 큐에 넣을 때 해당 명령어를 기억하게끔 하면 쉽게 처리할 수 있다. 다른 접근 방법으로는 prev 정보를 저장하는..

Approach 잘 생각해보면 최대 T번 누를 수 있다는 명제를 T번 이동할 수 있다로 바꾸고, 버튼 A와 B를 누르고 나오는 숫자를 기준으로 생각해보면 비둘기집의 원리에 따라서 총 99999가지 경우의 수 밖에 없다. 따라서 해당 숫자들에 대해서 BFS를 돌려서 이 문제를 해결할 수 있다는 아이디어를 쉽게 떠올릴 수 있다. A와 B 작동은 적당히 string과 int 사이를 왔다갔다 잘 변환시켜주면 된다. (stoi와 to_string을 잘 활용해주면 된다) Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; bool visited[100000]; int main(voi..

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