문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/87694
코딩테스트 연습 - 11주차
[[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10
programmers.co.kr
재미있는 구현 문제였습니다.
알고리즘은 아래와 같습니다.
1. 모든 직사각형의 테두리를 우선 방문 완료 표시해줍니다.
2. 모든 직사각형의 내부를 방문 제외해줍니다.
3. 1번과 2번을 완성하면 테두리가 완성이 되는데 (x, y), (x + 1, y) 좌표가 테두리로 설정이 되어 방문 완료 표시가 되지만 (x, y) -> (x + 1, y)로 가는 경로는 없고 (x, y) -> (x, y + 1) -> (x + 1, y + 1) -> (x + 1, y)로 가는 경로가 있는 케이스가 있습니다.
3.1 BFS를 적용할 경우 위와 같은 케이스를 판별하기 힘드므로 1번과 2번을 표시할 때 각각의 변을 두배로 늘린 뒤 표시를 해준다면 3번과 같은 케이스를 방지할 수 있습니다. 따라서, 1번과 2번 과정을 변의 길이를 두 배씩 늘린 상태로 진행합니다. (즉, 좌표를 두배씩)
4. 시작점부터 끝점까지 BFS를 진행하며 가장 빨리 도착한 경로의 길이를 반환해줍니다.
개발환경: 프로그래머스
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > programmers' 카테고리의 다른 글
[Programmers 위클리 챌린지 12주차] 피로도 (2) | 2021.10.25 |
---|---|
[Programmers] 나머지가 1이 되는 수 찾기 (0) | 2021.10.24 |
[Programmers 위클리 챌린지 10주차] 교점에 별 만들기 (0) | 2021.10.14 |
[Programmers] 빛의 경로 사이클 (0) | 2021.10.09 |
[Programmers] 없는 숫자 더하기 (0) | 2021.10.08 |