프로그래머스 아이템 줍기 풀이/해설 (파이썬) 간단한 코드! + 잡담

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

GitHub - Rhyankwon/algorithms

 

문제 설명

구현과 달리 문제는 간단하다. 여러개의 직사각형이 겹쳐져있는데 그 바깥쪽 라인만 따라서 한 지점에서 다른지점에서 이동하는데 그 최솟값을 리턴해야한다. 길이 하나로 연결돼있기때문에 경로는 총 두개가 나오고 그 중에 짧은거를 리턴하면 된다.

 

 

 

내가 생각한 문제 해결 논리

1. 그림에서 보면 알겠지만, 사각형들의 테두리가 다른 사각형과 겹치지 않은 경우, 그리고 테두리끼리 겹친 경우에는 합쳐진 도형의 바깥쪽 길로서의 역할을 한다. 그리고 테두리가 다른 사각형의 내부에 들어가는경우에는 더이상 그 역할을 할 수 없다. 따라서 각 사각형마다 외부격자, 내부격자를 따로 구분해서 저장해둔다.

2. 그렇게 되면 모든 테두리인덱스, 모든 내부격자인덱스가 나오는데, 이 테두리인덱스들 중에 내부격자인덱스와 중복되는 것들을 모두 빼면 합쳐진 도형의 맨 바깥쪽 테두리만 남는다.

3. 시작지점부터 위, 오른쪽, 왼쪽, 아래쪽 인덱스를 확인해서 만약 그 중 아무 하나 인덱스라도 '테두리인덱스 모음' 안에 있으면 그쪽으로 현재위치를 이동시키고 '테두리인덱스 모음'에서 이전 인덱스를 제외한다. 이 때 매번 인덱스를 옮길 때마다 카운트를 한다.

4. 아이템 인덱스(목적지)에 도착하면 카운트를 한번 저장하고, 다시 이동을 시작해서 시작지점에 도착하면 다시 카운트를 저장하고 루프에서 빠져나온다.

5. (목적지까지의 카운트, 전체 카운트 - 목적지까지의 카운트) 중 작은걸 반환한다. 

 

 

이 문제에서 어려운 부분은 개인적으로 첫째는 바깥쪽 테두리만 남기는거고 두번째는 예외처리를 하는거다. 4개의 사각형이 겹쳐서 내부에도 길이 생기는 경우는 크게 문제되지 않는다. 시작지점에 도착했을 때 프로그램을 종료하면되기 때문에 내부 길은 상관없다. 다만 정수 좌표만 고려하다보니 아래 그림처럼, 왼쪽으로 꺾여야하는 경우 그걸 무시하고 다른 좌표로 건너뛰어버리는 경우가 생겨버린다.

최대한 그림으로 잘 설명해보려 했는데;; 이해가 될지..모르겠다. 

 

나는 이부분때문에 거의 한시간 반동안 문제를 잡고있었는데 생각을 조금 해보고나서 해결법을 생각해냈다. x좌표와 y좌표를 0.5단위로 쪼개면 위 그림에서 B지점이 존재하지 않아서 원래 가야하는 길로 방향을 좀 더 세밀하게 조정할 수 있게 된다. 따라서 내 문제 해결 논리에서 정수격자만 카운트하지 않고 0.5간격 단위로 바깥쪽 길의 좌표들을 모두 저장해두고 정수좌표일 때에만 한칸씩 지나는걸로 카운트를 하면 문제를 풀 수 있다. 

 

 

 

----------------------------잡담-----------------------------

1. Lv3라 확실히 어렵다. 혼자서 레벨3 프로그래머스 문제를 푼게 오랜만이라 기분이 좋다. 시간이 오래걸리긴했어도..

 

2. 이렇게 0.5씩 움직이게 풀어야지-라고 생각을 해놓고도 이건 좋은 풀이가 아닌것 같다는 생각을 혼자 했었다. 근데 문제를 풀고 다른사람들 풀이를 보니까 아마도 이게 지금까지는 거의 유일한 풀이인가 싶다.

 

3. 다른사람들 풀이도 많이 봤는데 개인적으론 내 풀이가 마음에 든다. 이 얘기는 다른 풀이 쓸 때에도 그렇고 꽤 자주 쓰는 것 같은데 음.. 그냥 좀 간단한 느낌..?ㅋㅋㅋㅋ 다른사람들은 이렇게 생각 안 할지도..