알고리즘 일기장 - 1
프로그래머스 - PCCP 기출문제 - 수레 움직이기
퇴사를 하고 여기저기 여행을 다니는 와중에 차에서 흥미롭게 읽은 아티클이 하나 있다.
테오라는 분의 블로그에 있는 컴퓨팅 사고와 개발실력 늘리기라는 아티클이다.
아직 쉬면서 하고 싶은 공부를 하고 있지만, 추후 PCCP 알고리즘 시험을 신청하고 볼 생각을 가지고 있어 틈틈이 알고리즘 문제를 풀 계획을 가지고 있던 나는 해당 글의 원리를 바탕으로 아래 알고리즘 문제를 풀고 나의 기준에 맞추어 정리해 보려 한다.
프로그래머스 - PCCP 기출문제 중 lv3. 수레 움직이기 문제에 대한 풀이 글을 작성해 보려 한다.
문제 풀이 과정을 아래에 적힌 네 단계로 나눈 후, 의식적으로 분리하며 문제를 풀었다
1. 요구사항 분석 -> 2. 데이터적 설계 -> 3. 데이터를 기반으로 풀이 및 알고리즘 사고 과정 -> 4. 구현 및 추상화
요구사항 분석
먼저 문제의 상황과 요구사항을 분석해 보았다.
- 1. 빨간 수레와 파란 수레는 서로 다른 출발지를 가지며, 최종적으로 서로 다른 위치의 목적지에 도착하여야 한다.
- 2. 각 턴마다 빨간 수레와 파란 수레는 반드시 상하좌우 네 방향 중 한 칸으로 이동해야 한다.
- 3. 격자 밖으로는 이동할 수 없다.
- 4. 격자에는 벽과 칸이 존재하며, 벽으로는 이동할 수 없다.
- 5. 도착지에 방문한 수레의 경우 움직일 수 없다.
- 6. 자신이 방문했던 칸으로 다시 이동할 수 없다.
- 7. 빨간 수레와 파란 수레가 동시에 같은 칸으로 이동할 수 없다.
- 8. 두 수레가 인접해 있다가 서로의 위치를 바꾸는 형태의 이동은 불가능하다.
- 9. 빨간 수레와 파란 수레가 모두 도착지에 이동하는 최소 이동 횟수를 구하며, 불가능할 경우 0을 표현.
정리한 요구사항은 아래와 같다.
특히 1번의 반드시 이동해야 한다가 중요한 키워드이다.
데이터적 설계
문제를 풀기 위해 필요한 데이터를 정의해 보았다.
원시값 형태의 데이터는 글이 길어질 것 같아. 객체 형태의 자료만 글에 적겠다.
- 빨간 수레가 현재까지 방문한 격자를 기록하는 배열
- 파란 수레가 현재까지 방문한 격자를 기록하는 배열
- 격자 칸
기본적으로 이 세 가지의 객체 데이터가 필요하다.
4차원배열로 선언하면 빨간 수레와 파란 수레의 방문한 격자의 기록을 한 번에 할 수 있지만, 코드 가독성 및 메모리 할당이 불필요하게 커지므로 2차원 배열 두 개로 각자 분리했다.
데이터를 기반으로 풀이 및 알고리즘 사고
요구사항 분석과 이를 기반으로 데이터 구조를 설계하였으니 알고리즘과 문제 풀이과정을 생각해 보자.
경우의 수중 최적의 해를 찾는 형태의 문제이며, 격자의 크기가 최대 4*4 배열이기 때문에 DFS 알고리즘을 사용하여 전체 탐색을 기본으로 하되, 백트래킹을 섞어주는 방식으로 문제를 풀 수 있을 것 같다.
그러면 지금부터 dfs에 대해 정리해 보겠다.
DFS 함수의 파리미터는 다음과 같이 다섯 가지이다.
1. 빨간 수레의 위치 (y, x)
2. 파란 수레의 위치 (y, x)
3. 현재까지 움직인 횟수
4. 빨간 수레의 도착 유무
5. 파란 수레의 도착유무
DFS 함수의 중요 로직 정리
1. 전역에 answer라는 변수에 123456789라는 충분히 큰 숫자를 할당해 놓았는데, 빨간 수레와 파란 수레가 모두 도착지에 도착한 경우, 현재까지 움직인 answer보다 작을 경우, 전역값을 갱신하고 리턴한다.
2. 현재 빨간 수레와 파란 수레의 y, x 좌표를 가지고, 16가지의 경우의 수를 기반으로 다음 수레의 위치를 파악한다. (빨간 수레의 이동 경우 4가지 * 파란 수레의 이동 경우 4가지)
3. 요구사항에 적힌 경우들을 각자 함수로 분리한 후, 다음 칸으로 이동할 수 없는 경우, continue 시킨다.
4. 다음 이동 경우에 빨간 수레와 파란 수레가 도착지에 도착하는지 확인한다.
5. dfs함수를 재귀적으로 실행하기 전에, 빨간 수레와 파란 수레의 방문 배열을 방문 표시로 변경한다.
6. 새로 생성된 값을 기반으로 dfs함수를 실행한다.
7. dfs가 리턴되는 경우 방문배열을 다시 미방문으로 변경해 준다.
Solution 함수의 중요 로직 정리
1. 설루션 함수의 경우 초기 빨간 수레와 파란 수레의 위치 기반으로 dfs를 호출하는 진입점인데 이때 초기 두 수레의 위치를 방문처리 해주어야 한다.
2. answer값이 123456789인 경우, 빨간 수레와 파란 수레가 모두 도착지에 도달한 경우가 없는 것을 의미하기 때문에 0을 리턴한다.
https://gist.github.com/cws3299/0424f2c72c6e89c14ecdd67af53fcdb2
한창 첫 취준 할 때는 더 빨리는 풀었을 것 같긴 한데, 이제는 빨리 푸는 것보다 가독성 있고, 원칙을 지키며 풀어보고 싶다.
아직도 부족한 점이 많아서 더 열심히 해야겠다.
