백준 13460 구슬 탈출 2

문제 설명

이번 문제는 보드 안에 빨간색 파란색 구슬이 한 개씩 있고 기울일 수 있는 최대 횟수가 주어질 경우, 해당 횟수 내에 빨간 구슬을 먼저 구멍에 빠질 수 있다면 해당 기울인 횟수를 구하는 문제입니다.

• 구슬은 손으로 건드릴 수 없고, 중력을 이용해 왼쪽 오른쪽 위 아래로 기울여서 구슬을 움직여야합니다. 기울이는 동작은 구슬에 벽에 닿아 움직이지 않을 때까지만 합니다.
• 빨간 구슬과 파란 구슬은 한 칸안에 있을 수 없습니다.
• 빨간 구슬이 구멍에 빠진 뒤 해당 턴에 파란 구슬도 구멍에 빠지면 실패입니다.

 

문제 풀이

아이디어

브루트 포스

이번 문제는 구슬의 움직임에 따라 빨간 구슬 파란 구슬의 움직임을 모두 확인해야 하므로, 모든 경우의 수를 고려하는 브루트 포스 방법을 생각했습니다.

 

고려해야 하는 점

• 한 방향으로 기울였을 경우 움직이는 방향에 따른 구슬의 움직임
• 보드를 왼쪽으로 기울였을 경우, 구슬이 같은 행에 있다면 먼저 도착한 구슬이 벽에 닿고 다른 구슬이 그 구슬 옆에 위치하게 됩니다. 보드를 위 아래 왼쪽 오른쪽으로 기울일 경우 이러한 경우도 고려해주어야 합니다.
• 만약 빨간 구슬이 먼저 구멍으로 빠지더라도 파란 구슬이 해당 턴에 구멍에 빠지는지도 확인해야 합니다.

 

풀이

bfs

한 원소는 배열로 구성되었으며, [[빨간 구슬 행, 빨간 구슬 열], [파란 구슬 행, 파란 구슬 열], 기울인 횟수] 입니다.

bfs를 이용해 최소 횟수로 빨간 구슬만 구멍에 빠지는 경우를 구할 수 있도록 해주었습니다.

 

기울이기

방향에 따라 같은 행이나 열에 있을 경우를 유의하고, 기울인 방향으로 벽이 나타날 때까지 구슬을 이동시켜줍니다.

이동하는 과정에서 구멍을 만났을 경우 flag와 같은 변수를 통해 구슬이 구멍으로 빠졌는지 여부를 저장해줍니다.

 

빨간 구슬의 구멍에 빠진 여부를 flag==2 파란 구슬의 구멍에 빠진 여부를 flag==1로 정해서 이 flag값에 따라 반복을 계속해줍니다.

만약 한 방향으로 기울이기가 끝났을 때, flag값이 1 또는 2가 아니라면 queue에 현재 빨간 구슬의 행,열과 파란 구슬의 행,열과 기울인 횟수를 넣어줍니다.

flag값이 1일 경우 빨간 구슬만 구멍으로 통과한 경우이므로 현재까지의 기울인 횟수를 출력하고 while문을 break해줍니다.

flag값이 2일 경우 해당 턴에서 파란구슬이 구멍에 빠진 경우이므로 해당 경우는 무시하고 넘어갑니다.

 

위의 기울이기 과정을 왼쪽, 오른쪽, 위, 아래 방향으로 실시한 뒤 flag값에 따라 진행해줍니다.

 

 

 

해결

이번 문제는 구현에 집중한 문제로, 차근히 모든 조건을 만족하도록 풀어야되는 문제였습니다.

 

문제 링크 : https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/13460.py