알고리즘/BOJ
BOJ 16724 피리 부는 사나이(Python 3)
70825
2019. 1. 24. 10:13
반응형
https://www.acmicpc.net/problem/16724
문제 푸는 방식은 간단했지만, 이걸 생각해내는 과정이 참 힘들었던 문제다.
완전 탐색을 돌려서 아직 방문하지 못한 좌표를 만났다면 t+=1을 한 후에, 방문하는 좌표마다 숫자t로 체크해주고, 계속 이동하다가 만약 t로 체크된 좌표와 만났다면 SAFE ZONE을 하나 늘리고 함수를 종료하고(싸이클), 그게 아니라 t`(이전의 t)와 만나면 SAFE ZONE을 늘리지 말고 바로 함수를 종료하는 형식으로 해주었다.
Q) 왜 t`를 만나면 SAFE ZONE을 하나 늘리지 않고, 바로 함수를 나가나요?
(이해를 돕기 위한 그림)
A) 만약 t`가 싸이클이라면 t로 색칠된 좌표에서 이동하다가 결국 t`로 이동해서 t`의 싸이클을 돌 것이고, t`에는 이미 SAFE ZONE이 있기 때문에 추가를 하지 않아도 됩니다. 만약 t`가 싸이클이 아니라면 t`도 t``로 체크를 한 어떤 싸이클로 이동할 것이고, t``에는 이미 SAFE ZONE이 있기 때문에 이 부분 역시 굳이 추가를 하지 않아도 됩니다.
(문제에 어떤 경우에서든 지도 밖으로 나가는 방향의 입력이 주어지지 않는다고 나와있기 때문에 무조건 한 개 이상의 싸이클이 존재함)
재귀 함수를 이용해 문제를 풀었습니다.
반응형