디저트 카페(게리맨더링2 문제)
유혹을 견뎌내는 것은 유혹에 넘어가는 것보다 달콤하다.
정수 N 하나만 입력받는다 해도 입력받을 때 주의할 점! br.readLine()은 엔터까지 같이 입력되는 것 같다. 그래서 StringTokenizer의 .nextToken()으로 줄바꿈이나 공백문자 제거하고 난 후의 값을 쓰도록 하자! br.readLine()으로 바로 하지 말고! br.readLine()으로 바로 하면 Integer.parseInt()에서 줄바꿈문자를 정수형변환처리해버려서 오류난다!
문제 유형 : 재귀, DFS, 백트랙
재귀함수 : 현재 위치에서 이동할 방향을 선택한다.
현재 위치 (nr,nc), 현재 방향 dir ( dir은 문제에서 제시된 대로 ↘️↙️↖️↗️) 선택1. 재귀함수로 현재 위치에서 dir 방향으로 계속 이동한다.(방향초과하면 리턴되어 아래 선택2로) 선택2. (선택1에서 계속 이동하다가 범위가 초과하면) 방향 전환한다. (dir = dir+1로 재귀호출)
불가능한 경우 ① 범위 초과✅ ② 중복 디저트✅ ③ dir값이 4가지 초과⭐️ ④ 첫번째 좌표보다 x값이 작은 경우⭐️
정답 찾은 경우 첫번째 좌표로 다시 돌아온 경우 : 이동한 좌표(nr,nc)가 처음 좌표(tr,tc)와 동일한 경우.
현재 좌표 선택하고 다음 경우 호출
백트랙킹
↘️↙️ : 모두 아래로 내려가는 방향이지만, ↖️↗️ : 위로 올라가는 방향일 때, 처음 선택한 좌표보다 x값이 작을 수 없다.⭐️⭐️⭐️⭐️⭐️
문제 조건에서 동일한 디저트 종류 재방문하지 않기 때문에 이 부분도 중복체크하여 리턴하도록 한다.
재귀함수(DFS) 문제 특징과 문제에 따른 재귀함수 구조 짜기가 아직 연습이 많이 필요한 것 같다. 게리맨더링 문제처럼 꼭짓점1,2,3,4 각각의 가능한 범위와, 꼭짓점1에 따른 2의 선택가능한 좌표, 꼭짓점1,2에 따른 3의 선택가능한 좌표, 꼭짓점1,2,3을 선택하고 난 후 자동으로 계산되는 꼭짓점4의 좌표를 구하는 방식으로 접근했었다. 꼭짓점1,2,3,4의 유효한 범위 조건을 조건1,2,3,4라고 할 때, 조건1에 따라 조건2를 만족하는 꼭짓점2가, 그리고 그에 만족하는 조건3을 만족하는 꼭짓점3을 선택할 수 있는데 이러한 조건과 가능한 좌표를 선택하는 것을 어떻게 유기적으로 결합해서 사각형 경로를 결정지을 수 있는지 코드를 짜지 못했다.
1에 따라 2를 선택, 2에 따라 3을 선택.. 계속해서 유사한 선택을 반복하고, 방향만 달라진다. 재귀함수의 특징은 동일한 동작을 계속해서 반복한다. 따라서 이 문제는 재귀함수로 풀 수가 있고, 다만 재귀함수에서 재귀를 종료하는 조건(불가능한 조건, 정답 찾은 조건)과, 각 깊이에서 무엇을, 어떻게 선택할지를 고려해봐야한다. 각 깊이에서 무엇을 어떻게 선택? 현재 위치에서 다음 진행할 방향을 결정하여 이동한다.
2번째 풀었을 때 문제 풀이
문제 추상화 : 각 칸에서 방향 선택하면서 이동을 반복한다. 각 칸에서는 2가지 선택이 있다. ① 현재 방향으로 다음 칸 이동 ② 방향 전환해서 다음 칸 이동 이동하는 방향은 정해져있다. ↘️↙️↖️↗️ 순으로 이동한다.(델타어레이로 구현)
재귀함수dfs 구현 구체화 1. 불가능한 경우 ① 범위 초과 ② 이미 갔던 디저트 번호 ③ 첫번째 선택한 x좌표보다 작은 경우 ④ 방향벡터 4가지를 벗어나는 경우 : dir>3 2. 정답 찾은 경우 : 다음 이동한 좌표(nx,ny)가 처음 좌표(tr,tc)와 동일한 경우 : 정답 배열에 최댓값으로 갱신 3. 현재 위치에서 이동방향 설정한 후, 다음 경우 호출(현재 좌표의 배열값 디저트 번호 true로 마킹) ① 현재 dir 그대로 ② 방향 전환
2번째 풀었을 때 틀린 이유
불가능한 경우에서 이동하기 전의 좌표에 대해서만 ①,②,③,④ 를 해서 오답이 나오거나 배열 초과인덱스 에러가 났다. dfs 함수는 현재 위치에서 다음 이동할 방향만 선택해서 재귀함수를 호출하고, 호출된 재귀함수 내에서 이동할 방향 dir로 이동을 시킨다. 따라서 dfs 함수 내에는 이동하기 전의 (nx,ny)와 이동시키고 난 후의 (nx,ny) 동일한 변수로 2가지 좌표가(이동전,이동후) 존재한다! 그렇기 때문에 불가능한 경우 4가지를 이동하기 전과 후에 적절히 배치해야한다! =>아래 순서로 수정하면 된다. 로직을 잘 생각해보자! 1. 이동 전 (nx,ny) 디저트 true로 마킹 ⭐️dir 체크 2. 이동시키기 nx += dx[dir]; ny+= dy[dir]; 이동시킬 때 주의할 점! 4가지 방향만 존재하기 때문에 이동시키기 전에 dir 인덱스 체크먼저 해주어야한다! ⭐️정답 찾은 조건을 먼저 위치시켜서 정답 찾은 경우 리턴하여 백트랙킹한다! 3. 이동 후 (nx,ny) 에 대해 불가능한 조건 리턴 처리 =>범위 체크, 중복 체크, 첫번째 좌표와 x값 비교 체크
재귀함수 호출 시 중요한 점 : 현재 디저트를 선택했으므로 true로 마킹하고, 재귀함수가 리턴되고 나면 다음 선택을 위해 원복 처리해야 한다! 원복 처리하는 타이밍은 선택①과 선택②가 모두 끝난 위치가 된다. =>재귀함수는 ①동일한 방향으로 먼저 쭉 내려가고, 불가능한 경우에 도달하면 그 때 ②방향 전환(꼭짓점 하나 생성, 하나의 변 생성 의미) 을 반복하여 4가지 방향으로 4개의 변(?) 사각형 경로를 형성한다. 선택①②는 사각형 경로를 만들기 위한 한 셋트다!
이와 같은 시뮬레이션을 보면 알 수 있듯이(?) 선택①과 ②를 모두 한 후에 사각형을 형성할 수 있다.
그렇기 때문에 원복을 시키는 것도 선택①과 ② 사이에 하면 안되고, 선택①과 ② 이후에, 사각형을 형성한 이후에 원복해주어야한다!
Last updated
