'출발 공항과 도착 공항이 같지만 비용과 소요시간이 다른 티켓이 존재할 수 없다' 라는 조건이 언급되지 않았으므로
'출발 공항과 도착 공항이 같지만 비용과 소요시간이 다른 티켓이 존재할 수 있다' 고 생각하는게 더 자연스럽지 않을까요?
u에서 v로 가는 항공편 중
더 싸지만 오래 걸리는 경우/
더 비싸지만 빠른 경우/
두 경우 모두 현실에서 충분히 있을법한 일들이고, 자연스럽게 떠올릴 수 있습니다.
10217번 - KCM Travel
말씀하신것을 보고 제 의견을 뒷받침하기 위한 근거를 찾고있던중인데 그동안 제가 문제를 잘못봤었네요.
'단계별로 풀어보기' - '최단 경로' 파트에 다른 문제들을 보면 문제 속에 '두 정점 사이에 여러개의 간선이 존재할 수 있/없음'을 찾아보려고 했는데
실제로 해당 문구가 존재하는 문제 :
1753, 최단경로 : 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
9370, 미확인 도착지 : 교차로 사이에는 도로가 많아봐야 1개이다.
11404, 플로이드 : 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
존재하지 않는 문제 :
1504, 특정한 최단 경로 :
11657, 타임머신 :
1956, 운동 :
가 있네요. 제가 말씀드리고자 했던건, pichulia님의 말씀과 같이 실생활에서 해당 부분이 있을법한 내용이지만
다른 단계별 풀이 문제와 동일하게 해당 조건이 있다면 사람들이 연습하는데 있어 더 좋은 방향이 되지 않을까 의견을 제시하려던 것이었습니다.
하지만 제가 기억했던 다른 문제들에 명시된 조건은 '방향 그래프 or 비방향 그래프'였고, 해당 조건에 대해서는 없는 문제들도 있었네요.
번거롭게 하여 죄송하며 좋은 경험이 됐습니다. :)
댓글을 작성하려면 로그인해야 합니다.
jkh9615 6년 전
각 티켓의 출발공항 u, 도착공항 v이 같은 경우가 있습니다.
문제에는 '출발 공항과 도착 공항이 같지만 비용과 소요시간이 다른 티켓이 존재할 수 있다'는 조건이 없어서
문제를 푸는데 많이 헤맸습니다.
위 조건의 유무로 인해 풀이방법이 바뀔 수 있는데요,
위 조건이 있을경우 인접리스트로만 풀이가 가능합니다.
u,v가 같은 티켓이 있을줄 모르고 인접행렬로 풀다가 인접리스트로 풀어봤는데 풀리네요.
채점번호 : 22220843
위 번호는 인접리스트를 통해 정답을 얻은 번호입니다.
채점번호 : 22221084
위 번호는 기능 구현 없이 데이터만 불러오는 코드입니다.
동일한 u와 v가 들어올 경우 System.exit(1); 을 통해 런타임 오류가 나도록 짰습니다.