Baekjoon 13459 구슬 탈출 JAVA

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

13459번: 구슬 탈출

 

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2013459

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 map가 주어졌을 때 구슬을 굴려서 골인할 수 있으면 1을 아니면 0을 출력하는 문제다.

조건은 구슬은 2개가 있고, 빨간 구슬이 빠지면 성공, 파란 구슬이 빠지면 실패,

동시에 구멍에 빠져도 실패, 동시에 같은 칸에 있을 수 없고,

이동 횟수는 10회까지 이후는 실패, 이동은 한쪽 방향으로 벽까지 쭉 이동시킨다.

​

해당 문제는 알고리즘 스터디에서 추천을 받고 문제를 풀어보았는데,

지난주에 추천받고 시도는 했지만 해결하지 못했고,

약간의 힌트로 얻어서 문제를 해결하게 되었다.

​

힌트는 다 이동시키면 좌표를 통해 비교를 해서 하나를 한 칸 뒤로 보내줘야 하는 것과

테케가 안 커서 방문 체크를 안 해줘도 된다는 것이었다.

​

먼저 데이터를 저장할 클래스를 만드는 데 각각 구슬의 좌표와 cnt 값 총 5개의 값을 입력받는다.

이후 입력 처리를 하고 각 구슬 좌표를 저장한 뒤 큐에 넣고 bfs를 한다.

​

큐에서 빼낸 뒤 cnt 값이 10보다 크면 실패했으므로 0을 출력해 주고 끝내고,

만약 파란 구슬이 골인했으면 다음 반복으로 넘기고,

빨간 구슬이 골인(파란 구슬을 위에서 먼저 체크하기 때문에) 했으면 1을 출력하고 멈춘다.

​

이후 각 구슬들을 이동시키는데 테두리가 #으로 둘러싸여 있으므로 #과 같아지면 한 칸 뒤로

이동시키고 멈추고, 골인을 하면 해당 자리에서 멈춰준다.

​

이제 두 구슬들의 좌표값을 비교하는데 처음에 이 부분에서 둘 다 골인한 경우를 체크 안 해줘서

마지막 테케에서 틀렸었고, 둘 다 골인했는지는 하나의 좌표만 비교해 주면 된다.

​

이후 각 구슬들을 시작 좌표에서 현재 좌표까지의 거리 값을 저장한 뒤 비교해서

빨간 구슬이 크면 빨간 구슬이 더 많이 이동했으니깐 한 칸 뒤로 가고

파란 구슬이 크면 파란 구슬을 이동시킨 뒤,

큐에 현재 빨간 구슬 좌표, 파란 구슬 좌표, 이전 cnt+1값을 넣어주고

bfs를 계속 진행하면 문제를 해결할 수 있다.