[프로그래머스] 아이템 줍기

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/87694#

코딩테스트 연습 - 11주차

 

푸는데 약 5시간 정도 걸린... ㅠ 문제입니다.

글 작성시간 기준 수요일 오후 5시 반 정도 됐는데 지금까지 푼 사람이 총 101명이네요. (제가 101번째)

 

이 문제를 접근하려면 크게 세 단계로 나눌 수 있습니다.

1. 주어진 좌표를 이용하여 사각형의 테두리 좌표들을 구한다.
2. 사각형을 모두 겹친 후, 가장 바깥 테두리만 남기고 제거한다.
3. 시작점에서 도착점까지의 최단 거리를 구한다.

 

1번은 크게 어렵지 않습니다.

2차원 배열 board를 만들어 놓고, 네 가지 테두리에 포함되는 좌표를 기록하면 됩니다.

저는 좌하단-우하단, 좌하단-좌상단, 좌상단-우상단, 우하단-우상단 순서대로 테두리를 기록했습니다.

 

2번이 고민할 부분이 많습니다.

일단 사각형을 모두 겹치고 나면, 주어진 테스트 케이스에서 바로 유의할 점을 발견할 수 있습니다.

우리가 보통 배열에 기록하는 것은 격자 안에 표시를 남기는 것입니다. 하지만 이런 경우 구분을 할 수 없는 경우가 생깁니다.

문제의 예시에서 주어진 그림을 봅시다.

 

예시 그림

왼쪽 측면에 보시면 x좌표 3~4, y좌표 5~6 부분에 凹 모양으로 움푹 들어간 곳이 보입니다.

저 그림 상에서는 5와 6 사이가 분명하게 구분된 것으로 보이지만, 5도 마킹되어 있고 6도 마킹되어 있습니다.

1번에서 단순하게 배열에 입력했다면 y = 5와 y = 6이 이어져 있는 결과를 얻을 것입니다.

 

이를 해결하기 위한 가장 좋은 방법은 배열을 두 배로 키우는 것입니다.

각 좌표만이 아닌, 좌표와 좌표의 사이까지 마킹하도록 하여 연결을 분명히 하면 됩니다.

 

다음으로, 가장 바깥 테두리만 남기고 제거하는 방법은 어떤 것이 좋을까요?

저는 0,0으로부터 BFS를 통해 도달하게 되는 테두리를 마킹하고, 테두리를 만날 경우 queue에 넣지 않는 방식으로 진행하였습니다.

 

3번은 시작점부터 끝점까지 DFS를 통해 구할 수 있습니다.

 

배열을 두 배로 키웠으므로 x2 해주는 것에 신경쓰고, 오타에 조심하면 해결할 수 있는 노가다 구현 문제입니다.

 

저의 경우 BFS를 통해 접근하면, 코너의 안쪽 테두리는 기록이 되지 않는다는 문제점이 있었습니다.

따라서 대각선 이동의 경우 이동거리를 2씩 늘리며 탐색하도록 하였고, 이와 관련된 예외 처리까지 하였습니다.

 

채점 결과

 

알고리즘은 쉽지만 아이디어를 떠올리고 구현하기 까다로운 문제였습니다.