[SWEA] 2105. [모의 SW 역량테스트] 디저트 카페 JAVA 문제풀이

풀이

 

 

 

 

 

 

 

쉽게 생각했지만 생각보다 시간을 많이 들인 문제입니다.

 

저는 이 문제를 풀이할 때 DFS를 이용하여 풀이하였습니다.

6개의 매개변수 (i, j(현재위치), si와 sj(시작점), 0(방향 0), 1(길이 1))를 이용하였습니다.

 

 

 

항상 직사각형 모양으로 디저트 카페 투어가 이루어지므로 저는 가장 위쪽 모서리를

중심으로 잡고 오른쪽 아래↘ (dir==0), 왼쪽 아래↙ (dir==1), 왼쪽 위↖(dir==2), 오른쪽 위↗(dir==3)

 

이렇게  기준점에서 시작하여 ↘ ↙ ↖ ↗순서대로 순회한다면 원위치로 돌아올 수 있기 때문입니다.

 

이를 이용하여 DFS를 순회하게 되는데, 해당 위치의 디저트 번호를 방문했는지 확인하는 disert()배열과 함께 이동하였습니다.

 

 

 

먼저 방향이 0일때, 오른쪽 아래(↘)로 이동함과 동시에 왼쪽 아래(↙)로 이동하게 하였습니다.

이는 직사각형 한 변의 길이가 고정된 것이 아니기 때문에 가능한 모든 경우를 탐색하기 위함입니다.

 

그 다음 방향이 1일 때와 2일 때도 같은 조건을 주었습니다.

 

 

 

 

위 그림과 같은 형태로 검사해주는 것입니다.

 

 

그 다음, 마지막으로 방향이 3번일 때에는 오른쪽 위(↗) 방향으로 이동하게 되는데,

 

이 때 출발점으로 돌아왔는지를 확인하기 위해 시작점에서 DFS 함수를 실행할 때 넣어준 (si, sj) 변수와 일치하는지

 

비교해주면서 원위치에 도착했는지를 알 수 있게 해주었습니다.

 

길이가 4이상이면서 현재까지의 최대값보다 더 크다면 해당 값을 정답으로 바꿔주었습니다.

 

 

 

코드

 

 

 

 

 

 

 

 

 

 

 

 

 

출처

 

 

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy