A. 문제설명
https://www.acmicpc.net/problem/16197
16197번: 두 동전
N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, ��
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. N*M 게임판과 두 동전이 주어짐
2. 게임판에는 빈 공간, 동전, 벽이 있을 수 있음
3. 게임판을 조작하여 두 동전을 모두 상하좌우 같은 방향으로 움직임
4. 여기서, 동전의 이동조건은 아래와 같음
- 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
- 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
- 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다. 이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
5. 두 동전 중 하나만 떨어뜨리고 싶은 경우, 최소 몇번을 눌러야 하는 지 구하라
B. 접근법
DFS
맨 처음 이 문제를 보고는, BFS로 탐사하는 알고리즘을 짜려고 했었다.
그러나, 조건의 두 동전이 이동한다는 점, 그리고 '이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.' 이 조건, 즉 동전 위에 동전을 쌓을 수 있다는 점에 착안하여 게임판을 빈칸과 벽으로만 표시하고 두 동전의 위치를 DFS로 탐색하며 돌리는 경우 간단하게 구현할 수 있다.
C. 풀이
1. 먼저 입력받은 게임판에서 동전의 위치를 빈칸으로 바꾸고 두 동전의 위치만 따로 저장
2. 해당 두 동전의 좌표를 DFS 함수에 전달하여 탐사를 시작
3. 매 탐사마다, 두 동전의 좌표를 전달받아 동전이 떨어질지, 말지, 둘 다 떨어질 지 판단하는 chk_cond() 함수를 호출
4. 여기서, 둘 다 떨어지거나 DFS의 호출 깊이가 10이 넘어가면 종료
5. 동전이 하나만 떨어진 경우 최소인지 판별하여 전역의 minCnt 변수에 해당 카운트를 업데이트
6. 둘 다 안떨어진 경우, 4방향으로 탐사하여 벽인 경우 좌표를 그대로 두고 게임판 밖이거나 빈 칸인 경우 해당 좌표를 전달하여 dfs() 함수 호출
D. 내 코드
