Link | 백준 13460번 문제 : 구슬 탈출 2 📌 About 게임 보드의 크기가 최대 10 x 10이며 최대 10번의 움직임만 고려한다. 그렇기 때문에 BFS으로 충분히 해결할 수 있다. 하지만 이외의 상황 자체를 구현하는데에 시간을 소요해야 하는 문제이다. 📌 Solution 🚩 BFS 처리 먼저 BFS를 어떨게 구현해야 할지 생각해야 한다. BFS를 구현한 Queue에는 board 정보와 몇번째 움직임인지를 전달해야 한다. 이를 State class으로 정의하는데 이때 전체 board 정보를 전달하면 메모리가 낭비된다. 메모리 낭비를 줄이기 위해 공의 위치와 움직임 횟수만 저장한다. 공들의 시작 위치를 Queue에 우선 삽입하여 탐색을 시작한다. 만약 모두 탐색하였는데도 빨간공을 구멍에 삽입할 수 없으면 -1을 반환한다. State 처

Link | 백준 16946번 문제 : 벽 부수고 이동하기 4 📌 About 문제를 순서대로 해석하여 solution을 만들면 다음과 같다. Step 1. 1을 찾는다. Step 2. 1을 0으로 만들고 인접한 0의 개수로 다시 초기화한다. 그런데 위와 같은 방법으로 하면 시간 초과가 발생한다. 그 이유는 동일한 위치의 0들을 굉장히 여러번 탐색하기 때문이다. 예를 들어 1000 x 1000에서 테두리만 1인 경우를 생각해보다. 탐색만 하는데도 $O(N^2)$를 보인다. 그런데 테두리를 탐색할 때마다 내부의 998 x 998개의 0을 탐색해야 한다. 여기서 solution이 나온다. 1이 아니라 0을 탐색하는 것이다. 인접한 0의 개수를 구하고 0 묶음과 인접한 1에 추가하면 된다. 예제 2번을 보면 다음과 같다. ![](https://velog.velcdn.com/ima

Link | 1463번 문제 : 1로 만들기 Analyze 이 문제는 BFS를 통해 해결할 수 있다. X 객체에는 현재 숫자와 몇 번의 계산을 하였는지 저장되어 있다. 최초의 X는 초기 x 값과 step = 0을 저장한다. X들을 Queue에 저장하면서 BFS를 한다. 추가 계산이 가능하다면 각각의 계산 가능성을 판단하여 queue에 추가한다. 만약 queue의 첫 번째 X가 1이 되었다면 해당 X의 step이 최소 계산 횟수이다. Queue에 저장되는 X의 step은 갈 수록 커지기 때문에 처음으로 찾을 수 있는 x = 1의 step이 최소 step이다. Solution