가희배 코테에 나온 수인분당선 문제를 세팅한 이야기

 이 글은 가희와 수인분당선 문제를 어떻게 셋팅했는지에 대한, 그러니까 썰에 관련된 글입니다. 여기에 풀이는 자세히 적지는 않겠습니다. 제 레포 보시면 됩니다. 그리고 잘 정리된 블로그 글도 있으니, 그걸로 대신하겠습니다. 대신에, 어떻게 준비를 했고, 어떤 것을 평가하려고 했는지 상세하게 적어보겠습니다. 어떤 것을 평가하려고 했는지만 보시려면 5번째 단락부터 보시면 되겠습니다. 제 문제를 검수해 주신 검수진 분들에게 다시 한 번 감사의 말을 올립니다.

 

---

 사실 철도 문제는 2018년 숭고한이 진행되었을 때 부터 생각해 오던 것이였습니다. 모종의 이유로 출제를 하지는 못했지만요. 그로부터 3년이 지나고, 모란역에서 인천역까지 수인 분당선만을 타고 간다는 컨셉으로 문제를 기획하게 되었습니다. 그리고 23시 59분은, 시내 버스로만 당일치기 여행하는 컨텐츠를 보고 아이디어를 얻게 되었습니다. 문제는, 이걸 어떻게 서술을 할 것이냐는 것이였습니다.

 

 

 첫 서술에서 시작역, 도착역과 같이 이해할 수 없는 용어들이 난무했습니다. 열차가 운행을 시작하는 역이니까 시작역, 열차가 운행을 종료하는 역이니까 도착역 등으로 서술했습니다. 그런데, 이렇게 적고 나서 보니 오히려 더 헷갈리는 상황이 발생하였습니다. 시작역과 도착역이라는 용어는 없기 때문입니다. 시작역이 K210이고 도착역이 K233이다. 생각해 보니 들어본 적이 없었습니다.

 

 대신에, 열차가 운행을 마치는 역인 종착역이라는 용어는 어디선가 들어보셨을 겁니다. 이는 철도 용어 사전에서 명시가 되어 있습니다. 즉, 문제에 있었던 시작역, 도착역 등을 의도에 맞는 표준 용어로 바꾸었습니다. 그런데 그것으로 끝이 아니였습니다.

 

 하행은 서울을 시점으로 해서 종점으로 운행하는 방향을 의미합니다. 그러면, 수인 분당선은 쉽게 하행 방향을 예측할 수 있습니다. 청량리역이 서울에 있고 인천역이 서울이 아닌 지역에 있으므로, 청량리에서 인천으로 향하는 방향이 하행이 됩니다. 그런데, 이 정의만으로 명확하게 떨어지지 않는 예가 있습니다.

 

 

 경강선입니다. 모든 역이 경기도에 속해 있습니다. 이 방향은 하행일까요? 상행일까요? 남쪽으로 내려가니까 하행이라고 칩시다. 그러면 이런 경우는 어떨까요?

 

 이 방향은 상행일까요? 하행일까요? 이쯤되면 헷갈리기 시작합니다. 조치원이 대도시인 대전에 더 가까워서 하행일까요? 아니면 조치원에서 제천으로 가는 것은 북동쪽으로 올라가는 선형이니까 상행일까요? 헷갈릴 여지가 다분합니다. 상행과 하행을 구글링 해서 일일히 찾아야 하는 경험은 그렇게 좋지 않을 겁니다.

 

 하행에 대한 정보를 지나칠 정도로 자세하게 서술한 것은 이들 때문이였습니다. 처음 서술할 때에는, 당연히 청량리에서 인천으로 가는 것이 하행이지라고 생각해서 이러한 정보들을 모두 생략했습니다. 그런데, 저 예들을 보면서 그것이 잘못된 생각인지를 뼈저리게 느끼게 되었습니다.

 

---

 그런데, 하행 방향으로 갈 때 모란역의 다음역은 야탑역이고, 야탑역의 다음역은 이매역이고. 이런 정보를 문제에 일일히 다 적을 수는 없는 노릇입니다. 다행히도, 기차역들과는 다르게 수인분당선의 역들은 역 번호가 있고, 인접역들 끼리 일정한 역 번호 규칙이습니다. 즉, 수십개의 역에 대한 연결 정보를 단 1 ~ 2줄로 표현할 수 있습니다. 예를 들자면, 모란역은 K225이고, 야탑역은 K226입니다. 그러면 하행 방향으로 K225 다음역은 K226이다라는 설명이 가능합니다. 즉, 하행 방향으로 수인 분당선의 역 번호는 Kddd로 표현이 되고, ddd + 1이 DDD일 때, Kddd의 다음 역은 KDDD이다. 이 정도로 표현할 수 있습니다.

 

 그런데, 이렇게 했을 때 문제가 하나 있다면, 학익역입니다. 하행 기준으로 송도역 다음에 인하대역이기 때문입니다. 중간에 학익역이 빠진 형태인데요. 다음 역이 ddd+1인 조건에 어긋나게 됩니다. 저거에 대해서 따로 적으려면 조건도 길어지고 장황해질 겁니다. 즉, 문제의 여러 복잡도를 낮추기 위해서 학익역에도 열차가 멈춘다는 조건을 넣었습니다.

 

 

 대신 ddd가 272일 때에는 다음 역이 없으니, 이 부분은 배제한다는 것을 설명에 추가했습니다. 그러면 하행 방향에서 각 역의 다음역들을 정의한 셈이 됩니다. 이제 열차의 알고리즘을 설명해야 했습니다. 문제는 이것을 어떻게 잘 설명할 것이냐였습니다. 그리고, 추가적인 제약 조건으로 무엇을 걸어야 하는지였습니다.

 

 먼저, 열차의 알고리즘부터 도식화를 시켰습니다.

 

 

 간략하게 이런 로직을 반복했습니다. 종착역이면 운행을 종료하고, 그렇지 않으면 20초 후 다음 역으로 이동하고. 열차가 운행을 시작하는 역에서 출발 시각만을 고려할 수 있게끔 군청색으로 칠한 로직을 추가했습니다.

 

 

 그러면, 로직을 크게 3개 부분으로 나눌 수 있습니다. 하행 열차의 알고리즘을 설명하기 위해서 정확히 3개의 순서가 들어갔던 것과 관련이 깊습니다. 그리고 역에 도착한 시각으로부터 20초 후에 상황을 표현하기 위해서 그림 3을 추가했습니다.

 

 

---

 이렇게 해서 끝났나요? 네. 전체적인 것은 끝났습니다. 그런데, 아직 이러한 정보들 만으로 문제가 '완벽'한지는 잘 모르겠습니다. 왜일까요? 무궁화호 기차, 특히 출근 시간대 열차를 타 보셨으면 전광판에 지연 x분이 찍혀있는 것은 흔하게 보실 수 있을 겁니다. 맞습니다. 지연과 조착은 매우 중요한 요소였던 것입니다. 예를 들어, K233발 K272행 1번 열차가 08:20:00에 출발한다고 해 봅시다. 그리고, K210발 K233행 3번 열차가 K233에 8:19:00에 도착한다고 해 봅시다. 1번 열차와 3번 열차가 지연이 없다면, 3번 열차를 탄 경우에, 1번 열차를 탈 수 있습니다. 왜냐하면, 8시 19분에 도착했다면, 1번 열차가 출발하기 이전 시각이기 때문입니다. 그런데 3번 열차가 지연이 항상 없을까요? 만약에 3번 열차가 3분 지연되었다면 어떨까요?

 

 

 노란색으로 칠한 1번 열차는 이미 떠나고 없을 겁니다. 조착의 경우도 마찬가지입니다. 조착 x분을 한 경우에, 원래 탈 수 없는 열차를 탈 수 있게 되는 경우도 생깁니다. 그러니, 이것을 명시를 해 줘야 했습니다. 조착을 하거나 지연을 한 경우 몇 분이나 했는지. 그런데, 이렇게 되는 경우, 문제가 지나치게 복잡해질 수 있어서, 조착이나 지연은 없다는 조건을 추가했습니다.

 

 그러면 문제가 없을까요? 2개의 열차가 동시에 역에 들어올 수 있는 경우는 없을까요? 상식적으로 없다고 생각할 수도 있지만, 분당선 구간만 봐도 그러한 역을 쉽게 찾아볼 수 있습니다.

 

 

 이런 구조의 역이 몇 개 있다는 것입니다. 그림 3에서 언급된 K232와 K233이 이에 속합니다. 하행 열차 둘이 같은 시각에 동시에 있을 수 있는 구조입니다. 그러니, 특정 조건이 없으면 열차가 겹칠 수 있는 상황이 벌어질 수 있고, 추가적인 서술이 없다면 계속 열차가 겹치는, 상식적으로 말이 안 되는 상황이 발생할 수 있어요. 서술이 매우 복잡해 질 것은 자명했습니다.

 

 특정 열차를 먼저 보내고, 특정 열차를 x분 후에 보낸다. 이런 규칙까지 추가하면 이게 코딩테스트 대비 모의고사인지, 비문학 기술 지문인지 모를 겁니다. 이러한 문제는 하행 열차 둘 이상이 같은 역에 있는 경우는 주어지지 않는다는 조건을 넣어서 어느 정도 해소할 수 있었습니다. 지금 와서 다시 보니, 20초 조건은 그림을 더 잘 그릴 방법이 있었을 텐데. 라는 아쉬움이 조금은 남는 서술이였습니다. 이런 아쉬움을 통해 성장하는 것일 테니, 그러려니 하고 넘겨야 겠습니다.

 

---

 이제, 제가 이 문제를 출제한 의도를 설명해 드리겠습니다. 먼저, 이렇게 복잡해 보이는 문제가 있다면, 입력 예제와 아웃풋을 먼저 봅니다. 그런데, 해당 문제는 아웃풋에 대해서 딱히 설명이 없네요. 대신에, 문제에서 참고할 만한 힌트가 있습니다. 이것을 보았느냐, 안 보았느냐에 따라서 문제를 이해하는 데는 5조 5억배쯤 차이났을 것이라고 생각합니다.

 

 예를 들어 ~역이 K258이고 ~역이 K272라면. 이 구문이 있습니다. '예를 들어' 라던지, for example 이런 것은 언어 계열 문제들을 풀 때 도움이 되는지 개인적으로 잘 모르겠습니다만, 코딩 테스트에서는 결정적인 힌트가 될 수 있습니다. 이 정보를 통해서 어떻게 도식화를 시킬 수 있는지 봅시다. K258, K259, ... , K272 순서로 멈추게 된다. 이러한 구문이 있어요. 그러면 일단, 아래와 같이 도식화를 시킬 수 있어요.

 

 

 그러면 연결 관계는 바로 나옵니다. 그리고, 열차를 타고 최대한 인천역으로 빨리 가려면, 중간 역에는 최대한 안 내리면 됩니다. 문제는, 수인 분당선이 K209부터 K272까지 있다는 건데, 힌트 부분에서는 일부분만 주어졌다는 것입니다. 제한을 보면, 열차가 운행을 시작하거나 종료할 수 있는 역이 K210, K233, K246, K258, K272라고 되어 있습니다.

 

 이 역들에서는 어쩔 수 없이 내리거나 타야 하는 역이 됩니다. 이를 그래프로 표현해 보면 아래와 같습니다.

 

 

 그런데 K225는 어디 있을까요? 가희는 처음에 K225에서 열차를 타야 합니다.

 

 

 그러니 이 부분까지 반영하면 위와 같이 표현할 수 있습니다. 이제 이것을 K225부터 K272까지 가희가 타고 갈 구간으로 치환해 봅시다. 그러면, 아래와 같이 그릴 수 있습니다.

 

 

 결국, 문제와 힌트를 잘 읽고, 구간으로 떨어트릴 수 있는지 물어본 문제였습니다. 이제 각 구간이 s에서 e를 연결할 때, s에 도착한 시각을 계산한 다음에, s에서 e방향으로 가는 가장 빠른 열차를 구해서 e까지 가장 빠르게 가면 됩니다. 만약에 K225에서 K272행 열차가 가장 빨리 와요. 그 열차를 탄다면 어떻게 하면 될까요? 똑같이 생각하면 됩니다. K272행 열차 1번을 타고 K233까지 간 다음에 K233에서 내립니다. 어짜피 그 열차는 20초 후에 떠날 것이니, 10초 정도 머무르던지, 내리자마자 바로 타도 1번 열차를 탈 수 있습니다.

 

 이 점을 이용하면 보다 간단하게 구현할 수 있습니다. 즉, 문제와 힌트를 잘 읽고, 구간으로 떨어트려서 문제를 단순화 시킬 수 있느냐가 1번째 출제 의도였습니다. 2번째 출제 의도인, 시각 처리와 구간 처리도 그리 만만하지는 않지만, 빡센 구현 코테를 준비하신다면 연습해 보셔도 좋을 듯 싶습니다. 이 글이 출제라던지 검수에 도움이 되실 지는 모르겠지만, 출제를 하면서 이런 부분을 유심히 봤다 정도만 얻어가셔도 좋을 듯 싶습니다.