[백준] 16197.두 동전 (Swift)

[백준] 16197.두 동전 (Swift)

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

16197번: 두 동전

풀이

주어진 2차원 배열 위에서 최단 거리를 찾아야 하니 BFS 로 해결할 수 있는 문제입니다. 다만 일반적인 BFS 문제와 조금 다른 점은 2개의 포인트가 동시에 같은 방향으로 움직인다는 것입니다.

 

움직이는 동전 2개 중 오직 1개만 보드 밖으로 나가게 되거나 움직이는 횟수가 10 보다 커지면 BFS 는 종료되어야 합니다. 동전이 보드를 탈출하지 못하는 경우는 BFS 함수가 종료되지 않고 끝까지 실행되는 경우이기 때문에 BFS 함수 끝 부분에 -1 을 출력해주면 됩니다.

 

저희가 고려해야 할 점들을 정리하자면,

• 동전 2개 중 오직 1개만 떨어지는 경우를 고려한다
• 움직이는 횟수가 10이 넘어가면 함수를 종료한다
• 동전 1개가 벽을 만나더라도 나머지 하나가 벽을 만나지 않는다면, 움직이는 횟수는 증가한다
• BFS 도중 함수가 종료되지 않고 끝까지 진행된다면, 보드를 탈출하지 못한 것으로 간주한다

정도로 볼 수 있습니다.

 

해당 조건들을 신경써서 코드를 작성한다면 문제를 해결할 수 있습니다.

코드

Swift