[알고리즘] 백준 13460

문제 링크

 

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

풀이

 

 

풀이방법

 

보드를 최소 몇번 기울여서 빨간 공을 구멍으로 빼낼 수 있는지를 구하는 문제이고 BFS 알고리즘을 활용하여 풀이를 진행했습니다.

 

전반적으로 다음과 같은 과정으로 풀이를 진행됩니다.

 

1. 초기값 설정

2. 반복횟수와 빨간공, 파란공의 위치를 저장하는 큐에 초기값 추가

3. 큐에서 하나를 꺼내서 상하좌우로 보드 기울이기

4. 큐가 비어있거나 반복횟수가 10회 초과이면 -1 출력 후 종료

5. 상화좌우로 기울였을 때의 위치 값 검사

   5-1. 방문한 적이 있는 지

   5-2. 파란 공이 굴러 떨어지는지

   5-3. 빨간 공이 굴러 떨어지는지 -> 반복횟수 출력 후 종료 

6. 위치 값 검사를 통과한 값은 큐에 추가한 후 3번 과정부터 다시 반복

 

중요하게 생각한 점

 

• 보드를 기울임에 따라 변하는 값은 빨간 공과 파란 공의 위치
• 이 값을 따로 기억해두어 같은 동작이 반복되는 것을 방지해야 한다고 생각하여 visited 라는 Set으로 방문이력(?)을 관리
• 위, 아래, 오른쪽, 왼쪽으로 보드를 기울일 때 빨간공과 파랑공의 위치를 고려하여 먼저 기울여야 하는 공을 순서대로 움직이도록 해야 함
• 공은 움직일 방향이 빈 곳이 아닐 때까지 움직일 수 있음
• rollTheBoard, roll 메서드에 이러한 로직을 구현했는데 너무 하드코딩한것 같네요...