osnim   4년 전

이 문제를 풀면서 반례란 반례는 다 만나본 것 같습니다. 실제 시험장에서 이런 문제 만나면 문제가 만만해보여 섣부르게 도전했다가 반례 찾느라 시간 다버리고 점수는 얻지도 못할 것 같아요 ㅠㅠ

 첫날인 어제는 풀기 싫을 정도로 까다롭고 반례가 많아서 포기할까 했지만 둘째 날인 오늘은 풀려서 정말 다행이고 그 동안의 고통이 다 씻겨져 내려갔습니다.

먼저 제가 이 문제를 풀면서 쉽게 놓치는 부분을 정리해봤습니다. 

1. ↑ ← → ↓ 순서로 우선 순위를 정해서 BFS 를 탐색하면 안됩니다. 같은 거리에 있는 경우는 행이 낮은순서, 그것도 같다면 열이 낮은 순서로 우선순위를 정해야합니다. 왼 왼 왼 보다 오 오 위 가 먼저입니다.

2. BFS 탐색시 남은 한칸이고 그 한칸에 손님이 있을 경우를 고려해야 합니다.  마지막 칸에 도착할 때 큐에 손님이 없어서 BFS를 마무리하는 경우가 있는데 이렇게 작동되면 안됩니다.

반례

10 1 5000
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
5 5
10 10 5 5
정답 5000

3. 시작지점은 다르지만 각 손님의 도착 지점은 같을 수 있습니다. 저는 link라는 개념을 도입해 하나의 도착지점을 여러 개 갈 수 있게 만들었습니다.

4. 택시의 시작지점에 바로 손님이 있는 경우 입니다.

반례

6 1 2
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
3 4
3 4 2 5

정답 4

5. 아마 80퍼에서 '틀렸습니다'가 발생한다면 여기서문제가 생긴 것입니다. 손님을 태우고 이동 중 연료가 다 떨어진 칸의 주위가 벽으로 둘러 싸인 경우입니다.

목적지를 찾는 BFS함수에서 연료가 바닥난 시점이 벽으로 둘러 싸여있으면 큐에 다음 칸을 못넣어 큐가 비어있어 더 이상 BFS를 진행 못하고 while을 빠져나가게 됩니다. 여기서 -1을 출력하고 종료를 시켜야합니다.

반례

6 1 19
1 0 0 0 1 0
1 0 1 0 1 1
1 0 1 0 1 0
1 0 1 0 1 0
1 0 1 0 1 0
0 0 1 0 0 0
1 3
4 2 1 6

정답 -1

6. 런타임 에러 (TypeError)

만약 승객을 태우고 목적지를 찾는 함수를 사용하시는 분들중에  TypeError가 발생한다면 retrurn 값이 있는지 확인해보세요 저는 if문에서나 while문 안에서 반드시 끝날줄 알고 retrurn을 안넣어 주었더니 TypeError가 발생했었습니다.

7. 위 예제들과 아래 링크들에 있는 예제를 확인한다면 위 문제는 쉽게 해결할 수 있을 것입니다.

https://www.acmicpc.net/board/...

https://www.acmicpc.net/board/...

https://www.acmicpc.net/board/...

https://www.acmicpc.net/board/... 여기 첫번째 예제는 답이 -1 입니다.

https://www.acmicpc.net/board/...

https://www.acmicpc.net/board/...

https://www.acmicpc.net/board/...

8. 제 코드가 궁금하신 분은 여기로 방문해주세요

https://osnim.tistory.com/entr...

hynb13   4년 전

1번 감사합니다...

↑ ← → ↓ 이거 반례가 안 떠올라서 그냥 썼는데 7퍼센트에서 바로 틀려버리네요 허허

hky5820   4년 전

5번 반례 감사합니다.

저는 특정 위치를 기준으로 전체 MAP에 대한 distance map을 구현하여 운전자에서 손님, 손님에서 도착지까지의 거리를 구하는 방식으로 문제를 접근하였습니다.

이러한 방식은 distance map에서 원하는 위치까지의 거리를 구할 때 unreachable 값인지를 확인을 해주어야하는데,

저는 운전자에서 손님까지는 체크해주었는데, 손님을 선택한 이후에 도착지를 선택하는 과정에서 체크를 안해주었습니다.

5번 반례의 의도는 도착지를 가는 과정에서 unreachable이라는 특성 때문에 연료가 고갈되는 상황이라고 생각이 됩니다.

하지만, 저와 같은 방법으로 접근 하는 사람이 unreachable을 확인하지 않고 그냥 distance값을 쓰게 된다면,

5번 반례의 의도와는 다르게 그냥 연료가 부족해서 못가는 상황이라고 판단이 될 수 있습니다.

예를 들어 unreachable값을 MAP의 크기인 N^2로 설정하게 되면, 손님의 위치에서 도착지까지의 거리가 값 그대로 N^2가 되게 됩니다.

만약 연료가 맵의 사이즈 대비 무지막지하게 크다면 N^2는 그냥 갈 수 있는 거리이기 때문에 도달 가능하다고 나옵니다.

따라서 저와 같은 방법을 접근하는 사람들에게는 5번 반례의 초기 연료값을 최대값으로 주게 된다면, 아래와 같은 잘못된 정답을 얻게 됩니다. 

( 잘못된 정답 값은 신경써주지 말아주세요. 접근 방식에 따라 얼마든지 잘못된 값이 나올 수 있을 것 같습니다. )

질문 게시판에 있는 거의 모든 반례를 다해봐도 계속 80%에서 막히고, 심지어 5번 반례도 계속 정답값이 나와서 정말 난처한 상황이였습니다.

5번 반례를 계속 보다가 정말 다행히도 문제를 찾게되어 감사한 마음에 저와 같은 고민을 하는 분들에게 조금이나마 도움이 되고자 주절주절 썼습니다.

다시한번 감사합니다.

4번 반례 감사합니다. 이 문제 진짜 실수하기 좋네요..

tbd05050   2년 전

hky5820 님과 같은 풀이로 접근했고, 79%에서 막혔는데 덕분에 해결했습니다.

bezzi1654   1년 전

4번 때문에 저도 엄청 헤맸네요 .. 실제 시험장에서 풀었을 생각하니까 아찔 합니다 ㅜ

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