사다리 조작

가로선 정보를 어떻게 저장해서 활용할지, 사다리 게임 구현을 어떻게 해야할지 좀처럼 감을 잡을 수 없었다.

사다리를 종료하는 조건만 어렴풋이 생각해낼 수 있었다.(세로선 기준으로 가로선이 H에 도달하면 종료된다.)

💡문제 핵심 아이디어

1. 사다리를 N*H 크기의 2차원 배열로 나타낼 수 있다.

2. 각 칸에 대해 가로선을 긋거나/ 안 긋거나 2가지 선택할 수 있다. 다만, N은 최대 30, H는 최대 10이기 때문에 총 300개 칸이 존재할 수 있고, 각 칸은 2가지 선택이 있으므로 총 2^300 개의 경우의 수가 존재하고, 이것은 1억보다 매우 크다. 하지만 문제에서 가로선 갯수가 3개 보다 크면 -1을 출력하라고 했기 때문에 이 조건을 백트랙킹으로 처리하면 된다! 따라서, 이 문제는 재귀를 이용한 Brute Force로 풀 수 있다!

3. 가로선 정보 처리 ⭐️⭐️⭐️⭐️⭐️ 가로선 정보 = (a,b) : a행에서 b열 시작점, a행 (b+1) 끝점. 시작점 1로 마킹, 끝점 2로 마킹. =>시작점(1)을 만나면 오른쪽으로 이동 : col++;⭐️⭐️⭐️⭐️⭐️ =>끝점(2)를 만나면 왼쪽으로 이동 : col--;⭐️⭐️⭐️⭐️⭐️

4. 가로선 index는 단순히 정수가 아니라 이 index를 통해 가로선을 놓는 row와 column값을 구할 수 있다! (아래 표 참고)=> row, column값으로 가로선 놓는 처리 가능!!!⭐️⭐️⭐️⭐️⭐️

5. 어떤 것을 선택할 때 순서가 상관 없음=>외판원 순회2문제와 똑같은 조합 문제이다. ex) 외판원 순회2 : 0,1,2,3 = 1,2,3,0 = 2,3,0,1 = 3,0,1,2 따라서 첫번째 자리에 임의의 수를 고정하고 모든 가능한 순열을 구하면 된다. 이때 첫번째 자리수를 0으로 고정하고, 첫번째 자리가 0에서 1로 증가하면 첫번째 자리가 0일 때 모든 순열을 다 구한 것이고, 이것은 모든 순열과 조합을 구했다는 것을 의미한다!

1번과 2번 아이디어를 통해 index번째에 가로선을 놓을지 말지 결정하는 문제이고, 이것은 다음과 같이 표현할 수 있다.

2차원 배열에서 가로선 index는 다음과 같다.

	0	1	2	3	4
0	0	1	2	3	4
1	5	6	7	8	9
2	10	11	12	13	14
3	15	16	17	18	19
4	20	21	22	23	24
5	25	26	27	28	29

index가 9일 때, 세로선 갯수(N)에 따라 행이 바뀌기 때문에 index / N = 행, index % N = 열이 된다! 이 row, column 값을 이용해 가로선을 놓는 처리를 할 수 있다!!!

3번째 풀었을 때 잘한 부분 : 선택하는 문제인 것을 알아차렸고, 대부분의 함수는 구현했지만 정확도가 떨어졌다. 특히 사다리 게임 결과를 판단하는 부분에서 치명적인 실수(?)를 했고, 선택하는 재귀함수에서도 현재 가로선 놓는 경우의 로직을 분리해버리는 과오도 있었다. +α =>그래도 이제 선택 문제들은 어느정도 많이 푸니까(?) 이것도 당연히 원트 만에 맞을 줄 알았는데 경기도 오산이였다. 자만하지말고, 조건 꼼꼼히 처리하자. 재귀함수 void 타입만 주구장창하지말고, int 타입인 경우, 최솟값 또는 최댓값을 찾는 경우도 문제마다 처리하는 것이 어떻게 다른지 익히기. 어렵다....언제쯤 마스터할 수 있을까..후..

static int go(int cnt,int pos) {
		//1.재귀 종료 :정답 찾은 경우 + 불가능한 경우
		//1-1.정답 찾은 경우:현재의 cnt를 ans에 저장하고 바로 리턴.
		if(cnt == 3 || pos >= H*N) {
			if(check()) {
				return cnt;
			}
			return INF;
		}
		//2.현재 위치에서 사다리 위치 선택
		int ret = INF;
		int curX = pos/N; int curY = pos%N;
		if(curY<=N-2 && Map[curX][curY] == 0 && Map[curX][curY+1] == 0) {
			Map[curX][curY] = START; Map[curX][curY+1] = END;
			ret = Math.min(go(cnt+1,pos+2),ret);//현재 위치에서 선택한 경우 가로선 갯수 최솟값을 저장@
			Map[curX][curY] = Map[curX][curY+1] = 0;//원복처리
		}
		ret = Math.min(go(cnt,pos+1),ret);//현재 위치에서 선택안한 경우,가로선 갯수 최솟값  
		return ret;
	}

불가능한 경우, 현재 위치에서 선택할 때 2가지 경우에서 조건을 비교하는 값이 공통될 때가 있다. 현재 위치가 (x,y)라고 할 때, y<=N-2 이면 가로선 놓을 수 있다. 즉, 가로선을 놓을 때 위치 y값으로 가로선 놓는 조건 판단한다. 불가능한 경우 : 사다리 놓을 때, 가능한 마지노선 값은 y가 N-2일 때 = H*N가 N*H-2일 때 가능한 마지막 값. 정답의 경우, 불가능한 경우를 pos>=N*H 라고 했는데, 이렇게 해도 정답처리가 될 수 있는 이유는, N*H-2이상임에도 코드가 밑으로 내려가더라도 사다리 놓는 조건에서 걸러지기 때문인 것 같다.

최소한의 가로선 갯수를 구해야하기 때문에 최솟값으로 갱신하는 부분이 필요하다. 사다리 0개, 1개, 2개, 3개, 위치0,1,2,..모든 경우의 수를 다해보고, 각 경우마다 필요한 가로선 갯수들 중 최솟값을 정답 변수에 저장해야한다.

막혔던 부분 재귀함수를 정수형으로 리턴타입을 할 경우, 각 경우마다, 재귀함수가 다 실행되고 난 후 마지막에 리턴 값을 무엇으로 설정해줘야할지 막막했다. => 최솟값으로 갱신하는 것이기 때문에, 조건을 만족하지 않을 때는 그냥 INF 를 리턴하면 된다. 재귀함수가 최종적으로 INF를 리턴하면 -1을 출력하면 된다.

틀린 부분

1. 현재 위치에서 가로선 넣는 선택하고, 다음 경우 재귀호출할 때, 현재 경우의 수 선택하는 영역 내에서 호출해야한다. 그렇기 때문에 현재 가로선 넣기 위해 조건 체크하는 그 영역 내에 재귀함수가 들어가야한다! 정답 코드

   if(curY<=N-2 && Map[curX][curY] == 0 && Map[curX][curY+1] == 0) {
   			Map[curX][curY] = START; Map[curX][curY+1] = END;
   			ret = Math.min(go(cnt+1,pos+2),ret);
   			Map[curX][curY] = Map[curX][curY+1] = 0;//원복처리
   		}

   틀린 코드 : if문으로 사다리 놓을 수 있는지 조건만 검사해서 사다리 놓는 처리만하고 if문을 닫았다. 이 때!! 다음 사다리 놓을지 말지 결정하는 재귀함수 호출& 현재 경우 원복하는 부분 들어가야한다!

   if(curY<=N-2 && Map[curX][curY] == 0 && Map[curX][curY+1] == 0) {
   			Map[curX][curY] = START; Map[curX][curY+1] = END;
   }
   ret = Math.min(go(cnt+1,pos+2),ret);
   Map[curX][curY] = Map[curX][curY+1] = 0;//원복처리

2. 현재 위치에 사다리 놓을 때 조건 체크 [curX][curY], [curX][curY+1] 둘다 0인지 체크해야하는데 [curX][curY] 복붙하고 y값 +1 안해줘서 동일한 위치값을 2번 체크해서 틀림..복붙하면 수정 잘하자.......

3. i번 열 선택 시 결과 i 판단 메서드 check() : 나 : 처음 선택한 현재의 열 번호 i를 start에 저장하고, 사다리 만나면 START, END 에 따라 증가 감소 시키는 것을 반복문 변수인 j를 증가 감소시켜버렸다. 그래서 당연히 반복문을 제어하는 것에 영향이 갔을 것이고, 제대로 반복하지 않았을 것이다. 정답 : 처음 선택한 현재의 열 번호는 현재 반복문의 반복문 변수이다. 이 번호를 복사해서 col에 저장하고, 이 col값을 사다리의 START, END에 따라 증가 또는 감소시키고, 행이 H-1까지 도달하고 난후, 증가 감소된 최종 col값이 현재 반복문에서 열번호 i와 같은지 비교한다. 정답 코드 : 현재 열번호는 현재 반복문의 반복변수값 j이기 때문에, 처음 시작할 때만 이 j를 col에 복사하고, 사다리 만날 때마다 증가 또는 감소시켜주면 되는 것이다!

   static boolean check() {
   		int col,row;//난 처음 시작좌표를 start에 저장하고 반복변수인 j로 +- 했는데 정답은 그 반대였다.
   		for(int j=0;j<N;j++) {
   			col = j; row = 0;
   			while(row<H) {
   				if(Map[row][col] == START) col++;
   				else if(Map[row][col] == END) col--;
   				row++;
   			}
   			if(j!=col) return false;
   		}
   		return true;
   	}

   틀린 코드 : 리팩토링 : 현재 최종 증감된(사다리 게임 결과값)이 하나라도 원래 열값과 다르면 실패이기 때문에 if-else문으로 할필요 없이, 다른지만 검사하면 된다. 그리고 어차피 행을 증가시키는 반복문이 다 끝난 마지막 부분이기 때문에 굳이 continue처리를 핮지 않아도 다음 반복으로 넘어간다!

   static boolean check() {
   		int col,row;//난 처음 시작좌표를 start에 저장하고 반복변수인 j로 +- 했는데 정답은 그 반대였다.
   		//처음 시작할 때 열 번호를 저장해서 이 변수로 +- 하는 것이였다!
   		for(int j=0;j<N;j++) {
   			start = j; row = 0;
   			//col = j; row = 0;
   			while(row<H) {
   				if(Map[row][j] == START) j++;
   				if(Map[row][j] == END) j--;
   				row++;
   			}
   			if(j==start) continue;
   			else if(j!= start) return false;
   		}
   		return true;
   	}