BOJ_13459_구슬탈출

백준 #13459 구슬탈출

• 알고리즘 스터디 문제 풀이입니다.
• 백준 13459번 에서 풀어볼 수 있습니다.

문제설명

구슬이 두개 있는 장난감이 있을 때, 이를 상하좌우로 움직여 빨간색 구슬을 구멍으로 빼내는 문제이다. 단, 이때 파란색 구슬은 어떠한 방법으로도 구멍에 빠지면 안된다. 이 때, 빨간색 구슬만을 10번 이내의 움직임으로 꺼낼 수 있는지 없는지 알아내는 것이 문제이다.

풀이

이 문제는 흔한 그래프 완전탐색 문제이다. 하지만 구슬들이 움직이는 조건들이 까다롭기 때문에 조건을 잘 나누어 dfs로 풀이해주었다.

먼저 구슬을 움직일때는

1. 빨간색 구슬과 파란색 구슬이 겹쳐서 움직이지 않는 경우
2. 만나는 경우

크게 이렇게 나누어 주었고, 만약 1~2 과정에서 파란색 구슬이 빠진다면 이 상황은 실패한 경우이기 때문에 따로 구분을 해주었다.

그리고 이러한 조건을 주고, dfs의 최대 깊이를 10으로 하여서 백트래킹으로 완전탐색해주었다. 이 때, 중요한 것은 board(2차원 배열)을 그때마다 deepcopy해서 주게되면 시간초과가 나오기 때문에, 아래와 같이 dfs호출시마다 board를 임의적으로 수정해서 다음 dfs로 넘겨주는 방식으로 접근하였다.

.
.
.

board[red[0]][red[1]] = '.'
board[blue[0]][blue[1]] = '.'
board[hole[0]][hole[1]] = 'O'
board[rr][rc] = 'R'
board[br][bc] = 'B'
board[hole[0]][hole[1]] = 'O'

dfs(cnt+1, [rr, rc], [br, bc], d)

board[rr][rc] = '.'
board[br][bc] = '.'
board[hole[0]][hole[1]] = 'O'
board[red[0]][red[1]] = 'R'
board[blue[0]][blue[1]] = 'B'
board[hole[0]][hole[1]] = 'O'

.
.
.