jkjan   4년 전

질문 게시판 보니까

BFS로 상근이나 불을 직접 이동시키던데,

저는 이동시키는 거 없이 거리만 따졌습니다.

사각형을 둘러싸는 것을 exit이라고 생각했고,

*이 불이고 @이 상근이니까,

그리드 그래프를 그리면서

exit의 벡터를 만들고 *의 벡터를 만들고 상근이 위치를 저장한 다음

exit 벡터를 돌며 BFS를 해 상근이가 실제로 도달 가능한 출구와 거기까지의 거리를 찾고

그 도달 가능한 출구 중 * 들까지의 거리를 계산해서 그 출구와 상근이의 거리보다 같거나 크면 그 출구를 삭제합니다.

그리고 그 도달 가능한 출구가 0개이면 impossible 이고

아니면 거리 찾으면서 계산한 최소 거리를 리턴합니다.

이게 제가 로직 자체가 틀린 건가 싶은데,

그 질문 게시판에 있는 21개 TC랑 예제랑, 바로 앞에 출구 있는 경우랑 불 없는 경우랑은 다 맞습니다.


시간초과가 나면 제가 포기하고 질문 게시판에서 사람들이 구현한 로직을 쓸텐데

그건 아니고 그냥 틀렸습니다가 떠서 일단 로직 자체는 맞는 거 같다고 생각합니다.

문제는 그 로직을 교묘히 피해가는 몇 가지의 반례인데...

진짜 며칠 동안 찾아도 생각해낸 반례가 없어서 이렇게 도움을 청합니다.

한 번 봐주시고 좋은 아이디어나 허점 발견하시면 댓글을 꼭 달아주세요.

감사합니다.

댓글을 작성하려면 로그인해야 합니다.