백준 17071번 숨바꼭질 5

문제 링크입니다: https://www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

 

동생의 위치가 계속 움직이기 때문에 기존 숨바꼭질 문제들의 심화 버전이었습니다.

 

알고리즘은 아래와 같습니다.

1. 주어진 N이 너무 크기 때문에 `visited[수빈이의 위치][경과한 초]`와 같이 이차원 배열을 선언하지 못합니다.

1.1 이 문제의 핵심은 수빈이가 [+1, -1] 혹은 [-1, +1]과 같이 이초에 걸쳐 동일한 위치로 이동할 수 있다는 점이었습니다.

1.2 이로 인해, 홀수 초 또는 짝수 초에 동생이 특정 위치에 도달했을 때, 수빈이가 해당 위치에 이미 홀수 초 또는 짝수 초에 방문했다면 결국 두 사람이 만날 수 있다는 것을 의미합니다.

• 두 번째 예제를 들자면 수빈이는 17에서 출발해 [-1, -1] 움직이면 15에 2초 만에 도착
• 동생은 5에서 시작해 4초가 경과하면 15에 도착
• 수빈이가 2초 만에 도착한 15 지점에서 [-1, +1] 혹은 [+1, -1] 움직이면 4초에 동생과 15에서 만남
• 따라서 `visited[수빈이의 위치][경과한 초]`가 아닌 `visited[수빈이의 위치][경과한 초 % 2]`로 선언해 공간복잡도를 줄일 수 있음

 

2. 1번의 로직대로 BFS 알고리즘을 구현하면 AC 받을 수 있는 문제였습니다.

 

* 주의: N과 K가 동일할 때 예외처리를 해줘야 합니다.

 

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~