[2019 윈터코딩] 가장 어려웠던 코딩테스트 3번 문제 해설

스타트업에서 개발자 커리어를 시작하고픈 수많은 주니어들에게 꾸준한 채용 등용문이 되어주고 있는, 프로그래머스의 윈터코딩(Winter coding). 현재 1차 코딩테스트와 2차 실무 과제 제출을 모두 끝내고 본격적인 채용 프로세스 돌입을 앞두고 있습니다.

윈터코딩 무엇? 프로그래머스가 매년 운영하는 주니어 개발자 중심의 스타트업 채용 연계 프로그램. 여름에 진행할땐 서머코딩(Summer Coding)이라는 이름으로 둔갑. 2020년에도 진행하니, 스타트업 채용에 관심 있는 주니어라면 미리 어떤 프로그램인지 미리 확인 추천!

스타트업 개발자 커리어 시작하기 - 2019 Winter Coding(윈터코딩)

문제 다시보기

10/26(토)에 진행되었던 1차 온라인 코딩테스트 체감 난이도가 높다고 느낀 분들이 많았던 것 같습니다. 특히 서머코딩 이후로 한 번 더 지원했던 분들은 '이전보다 문제가 어려워졌다' 는 반응이 많았는데요. 총 3개의 문제 중 마지막 문제가 가장 난이도가 높은 편이었습니다. 우선 무슨 문제였는지 확인해볼까요?

2019 윈터코딩 코딩테스트 문제 중 마지막 문제입니다. 지문을 읽은 뒤, 풀이에 대한 감이 오시나요?

문제 내용이 바로 기억나는 분은 아래 설명으로 바로 내려가시고, 다시 한 번 문제를 보고 싶거나 처음 보시는 분들은 [ 여기를 눌러 ] 지난 코딩테스트에 출제되었던 문제들을 확인해보세요.

3번 문제 '지형 이동' 해설 

이 문제는 격자 형태의 지형이 주어질 때, 사다리를 놓아 모든 칸으로 이동할 수 있도록 하는 문제입니다. 이 때, 사다리 설치 비용이 최소가 되어야 합니다. 먼저, 플러드 필(Flood Fill)이나 BFS등을 이용해 사다리 없이 이동할 수 있는 연결된 영역들을 찾습니다. 다음은 입출력 예제 2번의 예시입니다.

입출력 예 #2

land	height	result
[[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]]	1	18

사다리 없이 이동할 수 있는 영역은 위와 같이 3개의 컴포넌트로 구분되며, ①, ②, ③과 같이 번호를 붙여 표현할 수 있습니다. 이때, 같은 번호가 붙은 칸은 같은 컴포넌트에 속합니다. 다음으로 각 컴포넌트 사이를 이동할 때 필요한 비용을 구해줍니다. 이는 다음과 같이 그래프 형태로 표현할 수 있습니다.

위 그림에서 중복되는 비용의 간선은 하나로 표현했으며, 같은 컴포넌트에 속하는 정점사이의 간선은 생략했습니다. 예를 들어 (3행 3열)에서 (3행 4열)로 이동하는데는 사다리 설치 비용이 10만큼 들며, 이는 ①번과 ③번 컴포넌트를 연결하는 간선의 비용이 10인 것으로 표현할 수 있습니다. 이와 같이 주어진 격자를 컴포넌트로 분리하고, 각 컴포넌트 간의 이동 비용을 간선으로 표현한 그래프를 만들었다면, 모든 컴포넌트를 하나로 이어주는 최소 비용은 MST(Minimum Spanning Tree)를 구하면 됩니다. 위 그래프의 MST는 아래 그림과 같습니다.

문제를 다시 풀어보려면?

프로그래머스 사이트 내에 '코딩테스트 연습' 메뉴에서 '모든 문제' 탭을 클릭하면 2019 윈터코딩 뿐만 아니라 이전 서머코딩에서 출제되었던 문제를 직접 확인하고, 풀어볼 수도 있습니다. 위 3번 문제는 [ 여기를 눌러 ] 확인해보세요.

서머코딩, 윈터코딩은 주니어 개발자들과 유수의 스타트업 기업을 이어주는 프로그램입니다. 매년 진행하고 있으며, 취업 준비생부터 총 경력 2년 미만의 주니어 개발자까지 모두 지원할 수 있습니다. >> 지난 2019 윈터코딩 소개 내용 보러가기 <<