pwr9258   4년 전

이 문제를 풀기 위해서

뱀이 머리를 꺾을 때의 좌표를 그래프의 노드로 삼고

해당 노드+1, 노드-1과만 edge가 연결되어 있다는 전제를 두어

새로운 노드가 생길 때마다 바로 전의 노드와의 edge 사이에

다른 노드들이 만든 edge가(가로라면 세로 edge와, 세로라면 가로 edge와) 교차하면 죽는 것으로 알고리즘을 설정했습니다.


예외적인 테스트 케이스를 처리하기 위해서 임의로 여러개를 만들어서 확인 결과

1. 벽에 부딪힐 경우 동서남북 모든 방향에서 사망한 것을 확인

2. 처음 시작점에 부딪힐 경우 가로X세로가 아닌 가로X가로 충돌이지만 사망하도록 처리

3. 여러 개의 edge들과 충돌할 경우 가장 먼저 충돌한 edge에 해당하여 사망시키게 처리

4. N에 0을 입력하더라도 i를 1줄 입력 받을 수 있게 처리

5. 입력이 끝났는데 뱀이 살아있을 경우 뱀이 계속 나아가 죽는 시간을 계산하도록 처리

이렇게 하여 4% -> 34% -> 63%까지 왔는데 이제는 어떠한 예외적인 케이스에 틀리는지 찾기가 어렵습니다.

틀리는 것으로 보아 분명히 예외적인 케이스가 존재한다는 건데

제가 임의로 만든 것들은 통과를 하니까 더 답답해서 혹시

어떤 상황에서 틀릴 수 있는지 도움 주시면 감사하겠습니다.

kdk8361   4년 전

8
11
1 L
4 R
1 R
8 L
1 L
8 R
1 R
8 L
1 L
6 L
10 R

40이 답인데 41이 출력되네요.

pwr9258   4년 전

감사합니다 덕분에 해결했습니다.

제가 처리했다고 한 예외사항 중에서

3. 여러 개의 edge들과 충돌할 경우 가장 먼저 충돌한 edge에 해당하여 사망시키게 처리

를 확실하게 하지 않았었네요

새로운 노드의 X축이나 Y축이 기존 edge들보다 작으면 예외처리가 되었는데 컸을때 똑바로 예외처리가 되지 않았었습니다.

도와주셔서 감사합니다 ^^

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