Approach 다익스트라를 2번 돌리는 것은 쉽게 파악할 수 있다. 이 문제에서 가장 중요한 지점은, 최단 경로를 전부 찾고 해당하는 최단 경로를 지우는 것이다. 이를 위해 기존의 parent를 1개만 저장해둔 것에서 vector를 통해 저장해두면, 최단 경우에 해당하는 모든 간선들을 찾고 지울 수 있다. 추가적으로, 포인터 등을 활용해서 간선을 조금 더 효율적으로 지울 수는 있다. (toysmars님의 제출 코드 참고) Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int mov..

Approach 그래프 탐색 관련한 문제라는 것은 문제를 읽자마자 쉽게 파악할 수 있다. 문제 상황에서 가장 크리티컬한 지점은 탐색과정에서 보석을 얼마나 가지고 있는지를 기억해야한다는 것이다. 왜냐하면, 보석을 얼마나 가지고 있는지에 따라서 방문할 수 있는 지역이 달라지기 때문이다. 따라서 BFS를 돌리는 과정에서, 보석을 얼마나 가지고 있는지를 기억하고 있으면 된다. 같은 지역에 있는 보석은 1번만 주울 수 있으므로, 비트마스킹을 통해 1개의 정수로 어느 지역의 보석을 가지고 있는지를 쉽게 저장해놓을 수 있다. 추가적으로 같은 지역을 방문하더라도 보석이 달라지면 경향성이 달라지므로, visited를 2차원 배열로 잡는다. 위 문제와 비슷한 느낌으로 이해해주면 된다. https://viyoung.tist..

Approach 문제에서 이동 횟수의 최솟값을 묻는 상황이므로, BFS를 바로 떠올려주면 된다. 다만, 이 문제에서 되게 독특한 지점은 각 이동하는 상황에서 키를 가지고 있는지 여부가 굉장히 중요하다. 따라서 키를 가지고 있는지 여부를 set으로 넘겨줘도 되지만, 비트마스킹을 활용해주면 숫자 하나로 모든 것을 판단할 수 있게 된다. 추가적으로 visited도 신경써야 하는데, 키가 달라진다면 기존에 방문했던 곳이라도 양상이 달라질 수 있기 때문에 visited를 3차원으로 잡아주면 된다. 다음 문제와 비슷하게 느낌을 받았으면 충분하다. (위 문제도 단순히 같은 위치를 방문한다고 해서 같은 의미는 아니므로 차원을 1개 늘렸다.) https://viyoung.tistory.com/334 [백준 2206번] ..

Approach 최소 몇 개 선택하는지를 묻는 것에서 BFS 냄새가 났으면 충분하다. 다만, 기존에 처리한 숫자들은 다시 중복해서 처리할 이유가 없으므로 일종의 visited를 처리해야하는데 숫자들의 숫자는 8!밖에 안되는데 해당 숫자들을 전부 다 담기 위해서는 훨씬 더 큰 배열의 크기가 필요하게 된다. 따라서 set 자료구조를 활용해서 처리해주면 된다. + 숫자가 1~8까지 존재하므로 해당 숫자 - 1을 처리함으로써 총 3개의 비트로 해당 원소를 방문하였는지를 처리할 수 있다. 숫자가 8개이므로 총 24개의 비트를 가지고 visited를 처리할 수 있는 것이다. 위의 접근 방법 같은 경우는 string 자료구조를 써야하는 반면, 이 방식은 int 자료형으로도 처리할 수 있기 때문에 메모리 측면에서는 우..

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