현대차 소프티어 [인증평가(1차) 기출] 차세대 지능형 교통시스템 풀이/코드 (파이썬), 까다로운 구현 문제

문제 코드만 궁금한 분은 깃허브 링크 눌러주세요!

GitHub - Rhyankwon/algorithms

 

문제 설명 ㄱㄱ

Softeer

문제 이해 자체가 조금 복잡한 문제이다. 현대자동차는 매번 약간 까다로운 구현을 요하는 문제를 내는 것 같고, 문제 이해도 쉽지 않은 것들이 다소 있다. 이 문제도 처음 봤을 때 이해하는데에만 시간이 꽤 걸렸다. 대충 말하자면 각 교차로마다 정해진 신호등이 4개씩 있는데 시간에 따라 다른 신호등을 이용할 수 있다. 출발점과 출발 방향, 정해진 시간이 주어진 경우 해당 차량이 갈 수 있는 교차로는 최대 몇개일까? 를 구하면 된다.

 

 

나는 두달에 걸쳐서 풀었다. ..ㅋㅋㅋㅋㅋㅋ그만큼 문제가 까다롭다기 보단 한번 풀어보고 안돼서 한달뒤에 다시  풀어보고 또 한달뒤에 한번 힐끗 보고 이런식으로 했더니 두달이 걸려버렸다. 추가 잡담은 맨 아래에 하도록 하겠다. 나름 잡담에 풀이 흐름을 서술하기때문에 문제 풀이만 보고 이해가 안되면 잡담도 읽어보길 바란다.

 

 

 

문제 해설 (dfs 혹은 bfs를 사용한 구현 문제)

 

1. 시작할 때에 시간 T = 0으로 하고 T = 0 인 지점에서 ,T = 0일때 사용할 수 있는 신호등을 확인한다. 갈 수 있는 좌표는 여러곳이 나오는데 그 좌표가 우리에게 주어진 맵 크기 안에 있는지 확인해서 맵 안에 있는 곳으로만 이동한다.

 

2. 이동된 위치가 확정되면 (갈 수 있는 교차로 수) + 1을 해주고, 이동된 위치에서 T = 1 (아까에서 1초만큼 지난 상태이므로) 일 때의 신호등을 확인해서 갈 수 있는 좌표를 확인하고 이동한다. 

 

3. 1,2를 계속 반복해서 T = t(주어진 시간)까지 갈 수 있는 모든 교차로를 확인한다.

 

4. 이 때 주의할 점이 있다. 문제를 보면 1,5,9번 신호등은 왼쪽에서 오른쪽으로 차량이 진입하는 경우에 대한 신호등이다. 따라서 만약 지금 차량이 아래쪽에서 윗쪽으로 A라는 지점에 진입했는데 A라는 지점의 현재 신호등이 1,5,9라면 이 차량은 더이상 이동할 수 없게 된다. 멈추지 않고 이동할 수 있는 경우에 대해서만 문제를 풀어야하기 때문에 진입 방향을 확인해야한다.

 

5. 적당한 가지치기를 해서 시간초과가 안 나도록 문제를 풀어야 한다.

 

 

 

================================================================

 

 

문제를 다 풀고 나면 쉬운 문제네? 싶은 문제이다. 다만 4번 조건을 처음 8월에 풀었을 때 간과해서? 풀지를 못했었다. 그리고 9월에 다시 한번 볼까.. 했을 때 4번조건을 찾아냈었고 그렇게 20점;;을 처음 맞게 됐다. 근데 그 이후로 내 방식대로 가지치기를 했는데 도무지 풀리지가 않아서.. 한동안 손놓고 있었다. 그리고 어제?다시 문제를 봤다. 여전히 뭐가 틀린건지 확인을 못 하다가..? 결국 dev.talk에 나온 다른사람 풀이를 살짝 참고해서 문제를 풀 수 있었다. 해당 링크는

Softeer

아 물론 내가 갖고있던 문제랑 위에 질문 남긴 분이 가진 문제는 조금 다르다. 나는, 다 잘 풀었는데 가지치기 조건을 틀렸었다. 난 현재 위치, (진입 시간%4)만 확인하면 된다고 생각했는데 진입 시간에 진입하는 방향! 을 같이 고려해서 가지치기 해줘야한다는걸 완전히 못 보고 있엇다. 아무튼 위에 질문 남겨주신 분의 코드를 뜯어본건 아니고, 댓글에 이런식으로 가지치기 하면 안된다고 누가 써놓은게 있어서 '음.. 이렇게 가지치기 하는거 맞는데..'라고 혼자 생각하다가 보니까 내가 진입 방향을 고려하지 않고있었다 ㅠㅠ 어쨌든 이렇게라도 풀어서 다행이다. 조건을 꼼꼼히 안 살핀 내 탓이 크다. 아무튼 8월, 9월에 풀려고 했던 문제를 지금에라도 풀게 되서 기분이 좋다 :)

 

 

+ 소프티어 3차가 오늘이다. 어제 당직이라서 지금 컴퓨터를 쓸 수 있고, 그래서 소프티어 3차 인증평가 신청도 했는데 보니까 웹캠이 필요하다고 해서 나는 인증평가는 안 보기로 했다. 웹캠 쓸수가 없어서.. ㅋㅋㅋ