문제

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

해설

N*M 크기의 보드를 4방향으로 기울여서, 파란 구슬과 빨간 구슬을 굴려 빨간 구슬만 구멍에 빠지게 하는 최소 횟수를 구하는 문제입니다. 현재 상태에서 4가지 방향으로 기울이는 4가지 경우를 탐색해 나가면 됩니다.

시간복잡도 계산

$3 \leq N, M \leq 10$ 이고 4방향으로 최대 10회 탐색하므로, 최대 uptime은 대략 $max(N, M) \times 4^10 \leq 10^{18}$ 입니다. 따라서 단순히 BFS와 Brute-force를 사용할 수 있습니다.

구현

입력을 받을 때, 구슬과 구멍의 위치는 따로 저장해 둡니다.

현재 상태를 기준으로

• 위쪽으로 기울였을 때 변화된 상태
• 오른쪽으로 기울였을 때 변화된 상태
• 아래쪽으로 기울였을 때 변화된 상태
• 왼쪽으로 기울였을 때 변화된 상태 이 4가지 경우를 BFS로 탐색해 나갈 수 있습니다. 최대 탐색 깊이는 10회 이하로 제한합니다.

1번 기울였을 때, 구슬은 벽이나 구멍을 만나면 더 이상 구르지 않습니다. 따라서

• 구슬이 구멍에 빠진 경우

  • 빨간 구슬이 먼저 구멍에 빠졌다면, 성공
  • 파란 구슬이 먼저 구멍에 빠졌다면, 실패

• 구슬이 벽에 닿은 경우

  • 빨간 구슬과 파란 구슬이 다른 경로로 굴렀다면, 아무 일도 없음
  • 빨간 구슬과 파란 구슬이 같은 경로로 굴렀다면, 구슬의 위치를 재조정

visit 배열을 사용해서 이전 상황과 중복된 위치에 구슬이 있을 경우 제외합니다.

소스 코드

http://boj.kr/47d4f461d3b842b2a33bf45952b0ae8a

코멘트

문제 자체는 전형적인 BFS문제지만, 각 경우에 대한 예외처리를 고민하는데 여러 시간이 걸렸습니다... 삼성 코드테스트를 기반으로 한 문제들은 전반적으로 까다로운 구현을 요구하는 것 같습니다. 침착하게 펜과 종이로 그려보면서 생각하는 것이 도움이 되었습니다.

---

참고