백준 13640번 구슬 탈출 2 (삼성 SW 역량테스트 기출문제)

사용한 알고리즘 : 백트래킹


정말 많이 까다로운 구현 문제였습니다.

먼저 info 라는 struct를 만들어 구슬의 위치와 구멍에 들어갔는지 여부를 체크할 수 있도록 만들었습니다.

이후 각 4방향을 먼저 설정한뒤, (왼쪽, 오른쪽, 위, 아래)
이 움직임을 돌려줄 GoDirect라는 함수를 구현해 주었습니다.
pair를 담는 Q를 만들어, 해당 공이 해당 방향으로 움직일 수 있는 만큼 움직일 수 있게 해주었습니다.

이때 빨간공(=1)과 파란공(=2)이 겹치는 경우는,  dfs함수에서 보정해 주었습니다.
dfs 함수에서 움직임의 횟수를 count 해주어서, dfs를 돌릴때마다 구하고자하는 값 (ans라는 이름) 을 최신화 해 주었으며, 횟수가 10번 이상이나, 기존에 최신화된 ans보다 클 경우는 제외해주었습니다.

백트래킹을 위해 visited라는 bool 함수로 빨간공과 파란공의 각 방문 위치를 기록해 주었고, 두 공의 위치가 (동시에 둘다) 방문 했던 위치라면 제외 해주었습니다.
이를 통해 백트래킹을 돌려주었습니다.

구현하는데 정말 오랜 시간이 들고, 많은 글들을 찾아본 문제였습니다.
계속 틀리더라도 끝까지 해보는 인내가... 많이 필요했습니다.