23030번 - 후다다닥을 이겨 츄르를 받자!
문제 해석에 관련된 부분이니 일반적으로 목적지를 정할 때를 생각해보면, 지하철을 통해 장소 X로 이동한다고 할 때 중요한 부분은 몇 번 출구로 나가는가가 핵심이라고 생각합니다.
A호선 지하철을 타고 목적지에 온 후에, 해당 역이 환승역이며 목적지는 B호선쪽 출구에 있다면 목적지에 도착하기 위해 걸리는 시간은 환승에 걸리는 시간을 포함하는 것이 맞다고 봅니다. (개인적인 경험으로 환승역이 목적지인 경우 역사 내에서 엄청나게 오래 걸어본 경험이 다수 있습니다)
이는 거꾸로 타는 입장에서 환승역에서 출발한다고 해도 마찬가지라고 생각하고요.
다만 문제 해석에 있어서 거리와 시간을 혼용해서 사용하고 있는 점은 수정되는 것이 맞다고 생각하고, 전부 시간을 의미하게 통일하면 어떨까 싶습니다.
먼저 답변 감사드립니다.
역사마다 고유의 출입구가 존재하는 환승역의 경우 어느 역사에 속한 출구로 역을 이용하는지가 이동 시간 사이에 영향을 미친다는 lcr님의 경험에는 충분히 공감합니다. 이용할 역사 또는 출입구에 따라서 구체적으로 경로를 설정하는 문제는 충분히 생각해볼 수 있는 문제이고, 실생활에도 도움이 되는 문제라고 생각합니다. 그리고 이 문제는 코드를 제출해본 결과 lcr님이 말씀하신 것과 같은 풀이를 요구하고 있다고 생각하고 있습니다.
다만, 실제 환승역의 경우 두 역사가 출입구를 공유하는 경우도 다수 존재하고 심지어는 수도권 지하철 금정역과 같이 하나의 역사에 두 노선이 같이 지나다니는 경우 또한 존재합니다. (저는 환승역은 "하나의 역"이라는 조건이 있어 금정역과 같은 역을 속으로 잠깐 생각하기도 하였습니다.) 또한 문제의 지문에는 각 역사에 고유의 출입구가 존재하여 그 역사에서 구체적으로 출발을 하거나 도착해야한다는 내용은 존재하지 않습니다. 따라서 이 문제를 푸는 선에서는 지하철을 이용하는 사람이 어떤 출입구를 이용할지 또는 역에 출입구가 어떠한 형태로 마련되어있는지와 같은 출입구와 같은 내용은 가정하기 어렵다고 생각합니다.
한편, 제가 지문을 해석할 때에는 네이버나 다음 등 포털사이트에서 제공하는 지하철 길찾기 서비스를 이용한 경험을 먼저 떠올렸습니다.
2021년 9월 12일 현재 네이버나 다음에서 "지하철 길찾기" 등으로 검색을 하면 지하철을 통해 두 역 사이의 경로를 추천해주는 서비스를 이용할 수 있는데, 역을 입력받을 때 두 서비스 모두 역의 이름과 노선정보를 함께 입력받고 있습니다. (이는 비환승역에도 적용됩니다.) 그러나 두 서비스 모두 경로를 추천할 때에는 처음에 입력한 노선의 역사가 어느 노선에 속하는지에 관계없이 경로를 소개하는 것을 알 수 있습니다.
예를 들어, 수도권 전철에서 2호선의 충정로역과 시청역은 한 정거장 간격의 두 역입니다. 또한, 충정로역은 2호선과 5호선의 환승역이며, 시청역은 1호선과 2호선의 환승역입니다. 두 포털사이트의 서비스에서 각각 5호선 충정로역을 출발지로, 1호선 시청역을 도착지로 설정한 경우를 살펴보겠습니다. 이 경우 각 포털사이트의 서비스는 검색 결과로 2호선 충정로역에서 지하철을 탑승하여 한 정거장을 이동한 뒤 2호선 시청역에서 내리는 경로를 보여줍니다. 5호선 충정로역에서 2호선 충정로역으로 환승 후 한 정거장 이동하여 2호선 시청역으로 이동한 뒤 1호선 시청역으로 환승하라고 소개하지는 않습니다.
위와 같이 현재 포털사이트의 지하철 길찾기 서비스는 저의 지문해석과 일치하는 방식으로 제공되고 있으며, 이 문제는 지하철 길찾기 서비스를 제공하는 어플을 소재로 하는 문제이므로 문제의 조건에 제가 못 찾은 제약사항이 없다면 없다면 이 또한 상식적인 선에서 나올 수 있는 하나의 지문해석이라고 생각합니다.
한편, 현재 맞았습니다를 받는 코드를 기준으로 그것이 정해가 되게 하려면 지문에서 "역"과 "역사"의 개념을 구분하여 서술(a 역사에서 b 역사로 이동)하거나 "두 노선 A, B의 역 a, b가 하나의 공통된 지점에 설치되어있는 경우 a는 b의 환승역이고 b는 a의 환승역이라고 한다."와 같은 방식으로 환승역의 정의에서 "하나의 역"이라는 문제의 조건을 제거하는 등의 방법으로 지문을 개선해야 할 것 같습니다. 만약 수정이 이루어진다면 지문을 저와 같이 오해하는 사람이 다시 발생하지 않게끔 출발지와 도착지가 환승역이더라도 입력으로 들어온 노선의 역(사)를 출발지와 도착지로 삼아야한다는 내용을 같이 서술해주는 것이 좋을 것 같습니다.
최단 거리 서술과 관련해서는 생각이 일치하는 것 같습니다.
혹시 제가 잘못 생각하고 있는 부분이 있는지에 대하여 알고싶습니다.
다시 한번 긴 글 읽어주셔서 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
measurezero 2년 전
문제 지문에서는 환승역을 4문단의 다음 문장과 같이 정의하고 있습니다:
이 지문대로라면, 환승역인 역은 하나의 역을 두 개의 노선이 공유하고 있는 역입니다. 즉, 역 X가 환승역이라면 X라는 하나의 역은 두 개의 노선 a, b가 지나고, 한 노선 위에서 X랑 인접한 어떤 역에서 X로 이동해왔을 때 같은 노선상의 인접한 역으로 이동한다면 이동시간이 1, 다른 노선상의 인접한 역으로 이동한다면 이동시간이 T+1인 역입니다.
따라서 출발지가 환승역인 경우 그 환승역을 지나는 두 노선중 어떤 노선으로 출발해도 상관없고, 도착지가 환승역인 경우 그 환승역을 지나는 두 노선중 어떤 노선으로 도착해도 상관없다고 생각합니다.
예를 들어, 노선이 지문의 그림과 같이 주어졌을 때 2호선3번역을 출발지, 3호선2번역을 도착지라고 할 때 2호선3번역과 1호선4번역은 두 개의 노선이 공유하고 있는 "하나의 역"이고 3호선2번역과 1호선5번역은 두 개의 노선이 공유하고 있는 "하나의 역"이므로 이동 시간 최솟값은 T값에 상관 없이 1호선 노선상에서 한 정거장을 이동하는 시간인 1으로 계산해야 한다고 생각합니다. 출발지는 "2호선3번역 = 1호선4번역" 이므로(환승역은 하나의 역이므로) 굳이 2호선3번역에서 1호선4번역으로 환승을 하며 출발할 필요가 없고, 마찬가지로 도착지는 "3호선2번역 = 1호선5번역" 이므로(환승역은 하나의 역이므로) 굳이 1호선5번역에서 3호선2번역으로 환승을 하며 도착할 필요가 없기 때문입니다.
그러나 오픈컨테스트에 참여하던중 이러한 풀이(제출번호 33237409; 아래의 소스코드)를 제출하여 틀렸습니다를 받았고, 오랜 시간 고민하다 위의 예제의 경우 마치 "2호선3번역 승강장"을 출발지로 하고 "3호선2번역 승강장"을 도착지로 하는 경로의 이동 시간 최솟값을 구하는 것과 같은 형태의 코드(제출번호 33237648)를 작성하여 맞았습니다를 받았습니다. 33237648은 아래의 구현에서 17번 줄을 지우고 38번 줄을 "return dist[e] - 1;"로 바꾼 코드입니다. 즉, 출발지와 도착지가 환승역으로 주어진 경우 환승역 관계에 있는 다른 노선의 역 또한 가능한 출발지 또는 도착지로 생각하는 구현을 제거한 것 이외에는 차이가 없는 코드입니다. boj 실험실의 소스코드 비교 기능을 이용하여 위의 두 줄을 제외한 다른 부분의 차이는 없다는 점을 확인했습니다.
출발지 또는 도착지가 환승역인 경우 제 생각과 같은 지문 해석을 제한하는 조건을 제가 놓쳤는지 알고싶어 질문을 드립니다.
추가로, 문제 지문의 마지막 문장인 "사용자가 환승 시간 T와 출발지, 도착지를 입력하면 최단 경로로 이동하였을 때 걸리는 소요 시간을 알려주는 프로그램을 만들어야 한다." 문장은 수정해야 합니다. 그 이유는 3문단의 "하나의 역에서 인접한 역사이의 거리는 일정하여 지하철을 통해 이동하는 데 모두 1만큼의 시간이 걸린다."라는 조건과 4문단의 "모든 환승역에서 걸어야 하는 거리는 동일 등 문제에 거리를 언급하는 조건이 여럿 있으며 이들의 대소가 주어져있지 않으므로 최단 경로가 무엇인지 알아낼 수 없는 경우가 존재하고, 알아낼 수 있다고 가정하더라도 출력 조건의 "출발지에서 도착지로 가는 최단 시간"과 "최단 경로로 이동하였을 때 걸리는 소요 시간"은 서로 같다고 보장할 수 없기 때문입니다.
긴 글 읽어주셔서 감사합니다.